Java Priority Queue优先级队列教程与示例

x33g5p2x  于2021-10-16 转载在 Java  
字(5.3k)|赞(0)|评价(0)|浏览(438)

Java 中的优先级Queue是一种特殊类型的Queue,其中所有元素都按照其自然顺序或基于创建时提供的自定义 Comparator 进行排序

优先级Queue的front 包含按照指定顺序最小的元素,而优先级Queue的rear 包含最大的元素。

因此,当您从优先级Queue中删除元素时,首先删除根据指定顺序的最少元素。

Priority Queue 类是 Java 集合框架的一部分,实现了 Queue 接口。以下是 Java 中 Priority Queue 类的类层次结构。

创建优先Queue

让我们创建一个整数优先Queue并添加一些整数。添加整数后,我们将从优先级Queue中一一删除它们,看看如何先删除最小的整数,然后再删除下一个最小的整数,依此类推。

import java.util.PriorityQueue;

public class CreatePriorityQueueExample {
    public static void main(String[] args) {
        // Create a Priority Queue
        PriorityQueue<Integer> numbers = new PriorityQueue<>();

        // Add items to a Priority Queue (ENQUEUE)
        numbers.add(750);
        numbers.add(500);
        numbers.add(900);
        numbers.add(100);

        // Remove items from the Priority Queue (DEQUEUE)
        while (!numbers.isEmpty()) {
            System.out.println(numbers.remove());
        }

    }
}
# Output
100
500
750
900

让我们看一下带有字符串元素的优先Queue的相同示例。

import java.util.PriorityQueue;

public class CreatePriorityQueueStringExample {
    public static void main(String[] args) {
        // Create a Priority Queue
        PriorityQueue<String> namePriorityQueue = new PriorityQueue<>();

        // Add items to a Priority Queue (ENQUEUE)
        namePriorityQueue.add("Lisa");
        namePriorityQueue.add("Robert");
        namePriorityQueue.add("John");
        namePriorityQueue.add("Chris");
        namePriorityQueue.add("Angelina");
        namePriorityQueue.add("Joe");

        // Remove items from the Priority Queue (DEQUEUE)
        while (!namePriorityQueue.isEmpty()) {
            System.out.println(namePriorityQueue.remove());
        }

    }
}
# Output
Angelina
Chris
Joe
John
Lisa
Robert

在这种情况下,首先删除按照字符串自然顺序的最小字符串。

使用自定义比较器创建优先级Queue

假设我们需要创建一个 String 元素的优先级Queue,其中首先处理具有最小 length 的 String。

我们可以通过传递一个自定义的 Comparator 来比较两个字符串的长度来创建这样一个优先级Queue。

这是一个例子——

import java.util.Comparator;
import java.util.PriorityQueue;

public class PriorityQueueCustomComparatorExample {
    public static void main(String[] args) {
        // A custom comparator that compares two Strings by their length.
        Comparator<String> stringLengthComparator = new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.length() - s2.length();
            }
        };

        /* The above Comparator can also be created using lambda expression like this => Comparator<String> stringLengthComparator = (s1, s2) -> { return s1.length() - s2.length(); }; Which can be shortened even further like this => Comparator<String> stringLengthComparator = Comparator.comparingInt(String::length); */

        // Create a Priority Queue with a custom Comparator
        PriorityQueue<String> namePriorityQueue = new PriorityQueue<>(stringLengthComparator);

        // Add items to a Priority Queue (ENQUEUE)
        namePriorityQueue.add("Lisa");
        namePriorityQueue.add("Robert");
        namePriorityQueue.add("John");
        namePriorityQueue.add("Chris");
        namePriorityQueue.add("Angelina");
        namePriorityQueue.add("Joe");

        // Remove items from the Priority Queue (DEQUEUE)
        while (!namePriorityQueue.isEmpty()) {
            System.out.println(namePriorityQueue.remove());
        }
    }
}
# Output
Joe
John
Lisa
Chris
Robert
Angelina

请注意如何首先删除长度最小的字符串。

用户定义对象的优先级Queue

在此示例中,您将学习如何创建用户定义对象的优先级Queue。

由于优先级Queue需要比较其元素并相应地对它们进行排序,因此用户定义的类必须实现 Comparable 接口,或者您必须在创建优先级Queue时提供 Comparator。否则,当你向优先Queue添加新对象时,它会抛出一个 ClassCastException

查看以下示例,其中我们创建了一个名为 Employee 的自定义类的优先级Queue。 Employee 类实现了 Comparable 接口并比较了两个雇员的薪水。

import java.util.Objects;
import java.util.PriorityQueue;

class Employee implements Comparable<Employee> {
    private String name;
    private double salary;

    public Employee(String name, double salary) {
        this.name = name;
        this.salary = salary;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public double getSalary() {
        return salary;
    }

    public void setSalary(double salary) {
        this.salary = salary;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Employee employee = (Employee) o;
        return Double.compare(employee.salary, salary) == 0 &&
                Objects.equals(name, employee.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, salary);
    }

    @Override
    public String toString() {
        return "Employee{" +
                "name='" + name + '\'' +
                ", salary=" + salary +
                '}';
    }

    // Compare two employee objects by their salary
    @Override
    public int compareTo(Employee employee) {
        if(this.getSalary() > employee.getSalary()) {
            return 1;
        } else if (this.getSalary() < employee.getSalary()) {
            return -1;
        } else {
            return 0;
        }
    }
}


public class PriorityQueueUserDefinedObjectExample {
    public static void main(String[] args) {
        /* The requirement for a PriorityQueue of user defined objects is that 1. Either the class should implement the Comparable interface and provide the implementation for the compareTo() function. 2. Or you should provide a custom Comparator while creating the PriorityQueue. */

        // Create a PriorityQueue
        PriorityQueue<Employee> employeePriorityQueue = new PriorityQueue<>();

        // Add items to the Priority Queue
        employeePriorityQueue.add(new Employee("Rajeev", 100000.00));
        employeePriorityQueue.add(new Employee("Chris", 145000.00));
        employeePriorityQueue.add(new Employee("Andrea", 115000.00));
        employeePriorityQueue.add(new Employee("Jack", 167000.00));

        /* The compareTo() method implemented in the Employee class is used to determine in what order the objects should be dequeued. */
        while (!employeePriorityQueue.isEmpty()) {
            System.out.println(employeePriorityQueue.remove());
        }
    }
}
# Output
Employee{name='Rajeev', salary=100000.0}
Employee{name='Andrea', salary=115000.0}
Employee{name='Chris', salary=145000.0}
Employee{name='Jack', salary=167000.0}

请注意如何首先删除最低工资的 Employee

结论

在本文中,您了解了什么是优先级Queue、如何使用优先级Queue、如何使用自定义比较器创建优先级Queue以及如何在优先级Queue中包含用户定义的对象。

相关文章

微信公众号

最新文章

更多