PriorityQueue是否真正有序

快来打我* 2022-05-15 02:43 222阅读 0赞

PriorityQueue是jdk1.5开始提供的优先队列，是一个优先“有序”的队列。通过其定义我们能得到如下特点：

1.元素有序，默认自然序，也就是数字默认是小的在队列头，字符串则按字典序排列，可以自定义comparator来自定义优先级

2.非线程安全，如果要并发修改要使用

java.util.concurrent.PriorityBlockingQueue

3.PriorityQueue是基于最小堆实现的数据结构，其逻辑结构是一棵完全二叉树，存储结构其实是一个数组。

4.PriorityQueue，也叫优先级队列，它是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。

看到这里我们会觉得那这是除了TreeMap, TreeSet等有序容器之外又一个有序容器。实际上真的是这样吗，我们通过一个例子看一下。

我们预期的输出是 \[10, 9, 5, 4, 2\]

实际的输出：

[10, 9, 5, 2, 4]

不是说是有序的吗，为什么输出不是完全有序的呢。

我们来看一下priorityqueue的实现，它是基于数组实现的最小堆，是一个完全二叉树，熟悉堆的特性的可以知道，最小堆只是保证左右子树大于堆顶元素，但是两个子元素谁大谁小并没有规定。也就是跟入队顺序是有关系的。

但是既然叫优先队列那么出队的时候通过poll方法拿到的元素是根据comparator定义有序的。通过poll方法让堆顶元素出列，然后会进行调整堆操作，调整之后，堆顶又是最小的元素。如此，一直出队，每次出队的都是当前堆里的最小元素（因为出队的是队头元素，而且是小顶堆，因此出队的肯定是最小元素），如此直至队列为空。就能让元素有序输出了。

再看下面的例子：

public class PriorityQueueFunc {
    
        public static void getPriQueueNumsAsc(){
            PriorityQueue<Integer> pqueue = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2.compareTo(o1);
                }
            });
            pqueue.add(10);
            pqueue.add(2);
            pqueue.add(5);
            pqueue.add(4);
            pqueue.add(9);
    
            System.out.println(pqueue.toString());
    
            System.out.println("===================");
    
            Iterator iterator = pqueue.iterator();
    
            while (iterator.hasNext()){
                if (pqueue.size() >1){
                    System.out.print(pqueue.poll() + ", ");
                }else {
                    System.out.print(pqueue.poll());
                }
    
            }
        }
    
        public static void main(String[] args){
            PriorityQueueFunc.getPriQueueNumsAsc();
        }
    
    
    }

这次的输出是：

[10, 9, 5, 2, 4]
    ===================
    10, 9, 5, 4, 2

就能看出来下面的是完全符合comparator规定的顺序了。

有一篇写的更全面的文章可以一看：

[https://www.jianshu.com/p/4c7ad59a0489][https_www.jianshu.com_p_4c7ad59a0489]

[https_www.jianshu.com_p_4c7ad59a0489]: https://www.jianshu.com/p/4c7ad59a0489