对Java中PriorityQueue迭代器打印顺序的深度研究

前言

一天我在学习JavaSE的时候，学到了PriorityQueue优先级队列这个东西，讲师说道

它这个将元素入队后会自动排序，出队的时候就会按大小排序。

然后我就试了一下，还真是，但是用迭代器打印其中的元素呢，发现事情并不简单…

问题

Queue<Integer> queue = new PriorityQueue<>();
queue.offer(10);
queue.offer(1);
queue.offer(5);
queue.offer(2);
System.out.println(queue);

可以猜一下，结果是什么，正常按理来说应该顺序是：

// [10, 1, 5, 2]

但是实际的顺序是

// [1, 2, 5, 10]

我一直对这个很迷惑，直到我在一个学算法的网站上学到了一个叫堆的东西

8.1 堆 https://www.hello-algo.com/chapter_heap/heap/#813

分析

// 10入队

       10
    /      \

// 1入队
       10            1
     /    \   ->   /   \  
    1            10

// 5入队
       1
    /     \
   10      5

// 2入队
      1               1
    /   \           /   \
   10    5    ->   2     5
  /  \  /  \      /  \
 2               10

最后对这个二叉小顶堆进行层序遍历得到

// [1, 2, 5, 10]

结论

优先队列PriorityQueue的底层数据结构是小顶堆。

每次入队时，相当于一次入堆操作。