java - PriorityBlockingQueue 什么时候对元素进行排序？

Question

我有一个包含元素列表的 PriorityBlockingQueue。我已经实现了 Comparable 接口(interface)并覆盖了 compareTo() 以定义哪个元素小于、等于或大于其他元素。

所以我想知道优先级队列是如何工作的，也就是说，它什么时候对其元素进行排序？自动处理队列中的任何事件(添加、删除、修改)？

谁能给我解释一下优先队列是如何工作的？我不清楚。

Answer 1

事实上，PriorityQueue(PriorityBlockingQueue 委托(delegate))根本不对元素进行排序 - 它使用 heap data structure反而。此结构仅保证根据请求提供最小(或最大)元素，并且不会实际对整个集合进行排序。

底层数据结构的工作方式是排序只是部分的(只做尽可能多的工作以确保最小/最大元素在堆的顶部)，并且在插入元素时完成或者当顶部元素被移除时。