Java——PriorityQueue用法（实现最大堆）

Java——PriorityQueue用法

PriorityQueue 是 Java 中基于优先级堆实现的一个队列，可以用来存储一组元素，并按照一定的优先级顺序访问这些元素。其中，优先级高的元素会被先访问。

PriorityQueue 类位于 java.util 包中，是一个泛型类，可以存储任意类型的对象。

在 PriorityQueue 内部，元素会被排序，排序规则由元素的自然顺序或者指定的 Comparator 决定。

PriorityQueue 支持以下操作：

• offer(E e)：将指定元素插入到队列中。
• peek()：获取队列头部的元素，但不删除该元素。如果队列为空，则返回 null。
• poll()：获取并删除队列头部的元素。如果队列为空，则返回 null。
• remove(Object o)：从队列中删除指定元素。
• size()：获取队列中元素的数量。

另外，需要注意的是，PriorityQueue 不支持随机访问操作。如果需要随机访问操作，建议使用其他数据结构，例如 ArrayList 或 LinkedList。

下面是 PriorityQueue 的使用示例：

import java.util.PriorityQueue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建一个空的 Priority Queue，默认元素按照自然顺序排序
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // 添加元素到 Priority Queue
        pq.offer(5);
        pq.offer(3);
        pq.offer(8);

        // 获取并删除队列头部的元素，按照优先级顺序输出
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 输出结果：3 5 8
        }

        // 创建一个自定义排序规则的 Priority Queue
        PriorityQueue<String> pq2 = new PriorityQueue<>(
                (s1, s2) -> s2.length() - s1.length()); // 按照字符串长度降序排序

        // 添加元素到 Priority Queue
        pq2.offer("apple");
        pq2.offer("banana");
        pq2.offer("cherry");

        // 获取并删除队列头部的元素，按照自定义排序规则输出
        while (!pq2.isEmpty()) {
            System.out.println(pq2.poll()); // 输出结果：banana cherry apple
        }
    }
}

在上面的示例中，我们创建了一个空的 PriorityQueue 对象，并依次添加了元素 5、3、8。然后使用 poll() 方法遍历该队列，并按照优先级顺序获取并删除元素。最终的输出结果为 3、5、8。

当使用 PriorityQueue 时，可以通过自然顺序或自定义 Comparator 来定义元素的排序规则。以下是一些示例：

1. 使用自然顺序排序的示例：

import java.util.PriorityQueue;

public class NaturalOrderExample {
    public static void main(String[] args) {
        // 使用自然顺序排序（整数）
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(5);
        pq.offer(3);
        pq.offer(8);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 输出结果：3 5 8
        }
    }
}

2. 使用自定义 Comparator 定义排序规则的示例：

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

public class CustomComparatorExample {
    public static void main(String[] args) {
        // 使用自定义的 Comparator 来定义排序规则（字符串长度降序）
        PriorityQueue<String> pq = new PriorityQueue<>(
                Comparator.comparingInt(String::length).reversed());

        pq.offer("apple");
        pq.offer("banana");
        pq.offer("cherry");

        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 输出结果：banana cherry apple
        }
    }
}

3. 使用自定义对象和 Comparator 示例：

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

class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }
}

public class CustomObjectComparatorExample {
    public static void main(String[] args) {
        // 使用自定义的 Comparator 来定义排序规则（按照年龄升序）
        PriorityQueue<Person> pq = new PriorityQueue<>(Comparator.comparingInt(Person::getAge));

        pq.offer(new Person("Alice", 25));
        pq.offer(new Person("Bob", 30));
        pq.offer(new Person("Charlie", 20));

        while (!pq.isEmpty()) {
            Person person = pq.poll();
            System.out.println(person.getName() + " - " + person.getAge());
        }
    }
}

在以上示例中，我们分别展示了使用自然顺序和自定义 Comparator 定义 PriorityQueue 的排序规则的几种情况。这些示例演示了如何根据不同的需求对元素进行排序。

当我们需要将 PriorityQueue 定义为最大堆时，可以使用 Collections.reverseOrder() 方法来反转元素的自然顺序或者指定的 Comparator，从而实现最大堆的效果。以下是一个示例：

import java.util.Collections;
import java.util.PriorityQueue;

public class MaxHeapExample {
    public static void main(String[] args) {
        // 使用 Collections.reverseOrder() 反转自然顺序，定义 PriorityQueue 为最大堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        maxHeap.offer(5);
        maxHeap.offer(3);
        maxHeap.offer(8);

        while (!maxHeap.isEmpty()) {
            System.out.println(maxHeap.poll()); // 输出结果：8 5 3
        }
    }
}

在这个示例中，我们使用了 Collections.reverseOrder() 方法来反转自然顺序，将 PriorityQueue 定义为最大堆。最终的输出结果为 8、5、3，符合最大堆的特性。