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

优先级队列的front包含按指定顺序排列的最小元素，优先级队列的rear包含最大的元素。

因此，当您从优先级队列中移除一个元素时，会首先移除按照指定顺序排列的最小元素。

Priority Queue 类是 Java 集合框架的一部分，并实现了 theQueue 接口。以下是 Java 中 Priority 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

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

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

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

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

假设我们需要创建一个 String 元素的优先级队列，其中首先处理 length 最小的 String。

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

这是一个例子——

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

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

用户定义对象的优先队列

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

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

请查看以下示例，其中我们创建了一个名为 Employee 的自定义类的优先级队列。 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 是如何被首先删除的。

结论

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