Java 的 PriorityQueue 与最小堆有何不同？

Question

如果您不能insertWithPriority，为什么他们要命名PriorityQueue？它看起来与堆非常相似。有什么区别吗？如果没有区别，那么为什么它被命名为PriorityQueue而不是Heap？

Answer 1

默认的PriorityQueue是用Min-Heap实现的，即栈顶元素是堆中最小的元素。

为了实现最大堆，您可以创建自己的比较器：

import java.util.Comparator;

public class MyComparator implements Comparator<Integer>
{
    public int compare( Integer x, Integer y )
    {
        return y - x;
    }
}

因此，您可以通过以下方式创建最小堆和最大堆：

PriorityQueue minHeap=new PriorityQueue();
PriorityQueue maxHeap=new PriorityQueue(size, new MyComparator());

Answer 2

对于最大堆，您可以使用：

PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());

Answer 3

Add() 的工作方式类似于 insertWithPriority。

您可以使用构造函数定义所需类型的优先级：

PriorityQueue(int, java.util.Comparator)

查看 https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/PriorityQueue.html

比较器给出的顺序将代表队列中的优先级。

Answer 4

其他答案中描述的默认行为

最小堆（默认）：

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

对于最大堆：

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((o1, o2) -> o2-o1);

Answer 5

来自 Java 文档

优先级队列表示为平衡二叉堆：queue[n] 的两个子级是queue[2*n+1] 和queue[2*(n+1)]。优先级队列按比较器排序，或按元素的自然排序排序。

---

这是使用 PriorityQueue 的 ma​​xHeap 和 minHeap 的工作代码 -

class HeapDemo {
    private final static int HEAP_SIZE = 10; //size of heap

    //INNER CLASS
    static class maxHeapComparator implements Comparator<Integer> {
        @Override
        public int compare (Integer x, Integer y) {
            return y-x; //reverse order
        }
    }

    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(HeapDemo.HEAP_SIZE); 
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(HeapDemo.HEAP_SIZE, new maxHeapComparator());  

        for(int i=1; i<=HeapDemo.HEAP_SIZE; ++i){
            int data = new Random().nextInt(100) +1; //number between 0 to 100
            minHeap.add(data);
            maxHeap.add(data);
        }

        System.out.print("\nMIN Heap : ");
        Iterator<Integer> iter = minHeap.iterator();
        while(iter.hasNext()){
            System.out.print(iter.next() + " ");
        }

        System.out.print("\nMAX Heap : ");
        iter = maxHeap.iterator();
        while(iter.hasNext()) {
            System.out.print(iter.next() + " ");
        }
    }
}

示例 o/p ：

MIN Heap : 20 32 37 41 53 91 41 98 47 86 
MAX Heap : 98 91 41 53 86 20 37 41 32 47 

Answer 6

来自 PriorityQueue JavaDocs< /a>：

基于优先级堆的无界优先级队列。优先级队列的元素根据其自然顺序进行排序，或者通过队列构造时提供的 Comparator 进行排序，具体取决于使用的构造函数。

优先级是队列中对象的固有属性。元素根据某种比较进行排序。要插入具有给定优先级的某个对象，您只需设置对象上影响排序的任何字段，并且 add() 它。

---

并且，正如 @Daniel 评论的那样，

一般来说，Java 对象是根据它们提供的功能来命名的，而不是根据它们的实现方式来命名。

Answer 7

来自 http://docs.oracle.com/javase /7/docs/api/java/util/PriorityQueue.html

基于优先级堆的无界优先级队列。优先级队列的元素按照其自然顺序排序，或者按照队列构建时提供的比较器排序

为整数、长整型、浮点型、双精度型、字符型、布尔型提供的比较器进行排序（即原始数据类型）自然排序是升序，这就是为什么 Arrays.sort(arr) {其中 arr 是原始数据类型的数组}按升序对 arr 的值进行排序。您可以使用比较器更改自然顺序

比较器可以通过两种方式使用

• 其中一种方式是DpGeek 展示了

• 另一种方法是使用匿名类。例如

Arrays.sort(arr, new Comparator<Integer>() {
     public int compare(Integer x, Integer y) {
         return y - x;
     }
});

• 如果您有 java8，则可以使用 lambda 表达式

Arrays.sort(arr, (Integer x, Integer y) -> y - x);

这会按降序对数组 arr 进行排序