PriorityQueue的内部排序

Question

我无法理解 PriorityQueue：

import java.util.*;

public class TryME {
    public static void main(String args[]) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>();
        q.add(3);
        System.out.print(q);
        System.out.print("");
        q.add(1);
        System.out.print(q);
        System.out.print("");
        q.add(9);
        System.out.print(q);
        System.out.print("");
        q.add(6);
        System.out.print(q);
        System.out.print("");
        q.add(2);
        System.out.print(q);
        System.out.print("");
    }
}

输出：

[3][1, 3][1, 3, 9][1, 3, 9, 6][1, 2, 9, 6, 3]

这种排序是在什么基础上进行的？

Answer 1

优先级队列以堆的形式实现，其中特定节点的所有子节点的优先级都低于其父节点，但不一定是其兄弟节点的优先级。

元素存储在数组中（我怀疑）如下：

对于每个节点，子节点存储在 2*pos 和 2*pos+1 中。因此，对于 [1, 2, 9, 6, 3]：

element 1 (value 1), children are 2 and 9.
element 2 (value 2), children are 6 and 3
element 3 (value 9), 4 (value 6) and 5 (value 3) have no children...

如果从队列中删除，父节点将被具有最高优先级的子节点之一替换，该子节点又被其子节点之一替换，依此类推。（操作非常优化，只需 O(log n) 运行时间）例如：

[1, 2, 9, 6, 3]
[2, 9, 6, 3]
[3, 9, 6]
[6, 9]
[6]

列表已排序，它仅位于堆中，当将其打印为列表时，这一点并不明显。

Answer 2

javadoc 说：

该类及其迭代器实现了所有可选方法
Collection 和 Iterator 接口。中提供的迭代器
方法 iterator() 不保证遍​​历到的元素
任何特定顺序的优先级队列。如果需要有序遍历，
考虑使用 Arrays.sort(pq.toArray())。

如果执行，

while (!q.isEmpty()) {
    System.out.println(q.poll());
}

您将看到元素确实已正确排序。

Answer 3

PriorityQueue 按优先级顺序维护事物。您取出的第一个元素具有最高优先级。这很可能是使用 堆数据结构 实现的，它按顺序提供数据，但无需完全排序（这比每次重新排列内容可以更有效地插入和删除）。

作为消费者，对于优先级队列来说，内部顺序对您来说并不重要。您应该只从中获取元素并确保它们具有最高优先级。内部结构不是您应该关心的事情（请参阅 JB Nizet 指出的 Java 文档）。

Answer 4

在过去的 7 年里，我没有用 Java 做过任何事情，但顺序很可能是某种

然而，正如其他回复中所指出的，Java 如何在内部对元素进行排序对您来说并不重要，您只希望元素以正确的顺序出现（即优先级较低/较高）。

Answer 5

基本上，它没有排序。优先级队列实现通常会摊销排序成本 - 它们会花费最少的精力来确保以正确的顺序检索元素。每次提取一个元素足以选择最高优先级元素时，它都会进行部分排序。队列永远不会完全排序。

如果您调用 poll() 来提取数字，而不是打印整个队列，您将按照您期望的顺序获取它们。

Answer 6

 That particular method is used to sort the priority based index.
 When that remove method will call it will find the highest priority index.
       ```java  public Comparable remove(){
                if(index == 0){
                    System.out.println("The priority queue is empty!!");
                    return null;
                }
                int maxIndex = 0;
                // find the index of the item with the highest priority 
                for (int i=1; i<index; i++) { 
                    if (pQueue[i].compareTo (pQueue[maxIndex]) > 0) { 
                        maxIndex = i; 
                    } 
                } 
                Comparable result = pQueue[maxIndex]; 
                System.out.println("removing: "+result);
                // move the last item into the empty slot 
                index--; 
                pQueue[maxIndex] = pQueue[index]; 
                return result;
            }
 ```