PriorityQueue 是 java.util 包中一个常用的堆排序数据结构,初始化时需要传入一个 Comparator 接口实现。

由于我经常忘记 java 优先队列中的顺序(升序或是降序),也没有找到比较详细的记录这个问题的内容,故自己记录一下。

优先队列实际上维护了一个偏序集合,使用泛型指定的类是这个集合的定义域,而提供的 Comparator 接口实现作为这个偏序集合的偏序关系(满足自反,反对称和传递性,具体可以:偏序关系 - 维基百科,自由的百科全书 (wikipedia.org))。

优先队列中的元素始终按 Comparator 中的偏序关系升序排列,即从前往后地任意位置依次取出两个元素 a, b 始终满足 $a \leq b$ 。这种关系在 Comparator 接口上的表现即为 compare(T a, T b) 的返回值将始终小于等于 0。