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

这个列表是非常有序的，它只是在一个堆中，当我们将它作为一个列表打印时并不那么明显。