时间戳

首页 > 解决方案 > Java PriorityQueue 如何对元素进行排序

java - Java PriorityQueue 如何对元素进行排序

问题描述

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

Java代码：

PriorityQueue 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]

标签： javacollectionspriority-queue

解决方案

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

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

如您所见，它明确提到它基于优先级堆。现在，如果您想了解什么是堆，可以参考Binary Heap，或者如果您想了解基本上有 3 种堆类型 -> Min & Map，可以参考一行。Java 的优先级队列使用最小堆，在这种情况下

在二叉堆中存在的所有键中，根的键必须是最小的，并且对于同一棵树中的所有节点，相同的属性必须递归地为真

要实现这个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;
}

推荐阅读