Java PriorityQueue如何排序元素

Question

我正在使用优先级队列编写一个简单的程序，我在其中向其中添加元素，但我不知道它是如何在内部对元素进行排序的（java 文档说它是基于自然排序顺序的，但是如何？).

Java代码：

优先队列 pQueue = new PriorityQueue();

    // Adding items to the pQueue using add()
    pQueue.add(10);
    pQueue.add(20);
    pQueue.add(15);
    pQueue.add(50);
    pQueue.add(3);
    pQueue.add(2);

输出为： [2, 10, 3, 50, 20, 15]

Answer 1

你做对了，但部分是因为你错过了第一部分。

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

正如你所看到的，它清楚地提到它是基于优先级堆的。现在如果你想了解什么是堆，你可以参考 Binary Heap 或者如果你想了解基本上有 3 种类型的堆 -> 最小值和映射。 Java 的优先级队列使用的是最小堆，在本例中

the key at root must be minimum among all keys present in Binary Heap and the same property must be recursively true for all nodes in the same tree

要实现这个 java 也使用位移：

private static <T> void siftUpComparable(int k, T x, Object[] es) {
    Comparable key;
    int parent;
    for(key = (Comparable)x; k > 0; k = parent) {
        parent = k - 1 >>> 1;
        Object e = es[parent];
        if (key.compareTo(e) >= 0) {
            break;
        }

        es[k] = e;
    }

    es[k] = key;
}

Java PriorityQueue如何排序元素

How Java PriorityQueue sorting elements

java

collections

priority-queue