在Java中对优先级队列进行排序 [英] Sorting Priority Queue in Java

问题描述

我试图在 PriorityQueue 中插入整数，我知道：

I was trying to insert the integers in PriorityQueue, and I know that :

如果当构造 PriorityQueue 时，不指定比较器，然后使用队列中存储的数据类型的默认
比较器。默认比较器将以升序排序
队列

If no comparator is specified when a PriorityQueue is constructed, then the default comparator for the type of data stored in the queue is used. The default comparator will order the queue in ascending order

但是，我得到的输出不是按排序顺序排列的。
运行以下代码后的输出为： [2,4,8,6]

However, the output I am getting is not in sorted order. Output after running the below code is : [2, 4, 8, 6]

public static void main(String args[]) {
    PriorityQueue<Integer> q = new PriorityQueue<Integer>(10);
    q.offer(4);
    q.offer(2);
    q.offer(8);
    q.offer(6);

    System.out.print(q);
}

有人可以解释原因吗？

推荐答案

PriorityQueue 是所谓的二进制堆。它只是在第一个元素最少的意义上排序/排序。换句话说，它只关心队列前面的内容，其余的是在需要时排序。

A PriorityQueue is what is called a binary heap. It is only ordered/sorted in the sense that the first element is the least. In other word, it only cares about what is in the front of the queue, the rest are "ordered" when needed.

元素只有在它们出列时才被排序，即使用 poll（）从队列中删除。这就是为什么PriorityQueue能够获得如此优异的性能的原因，因为它不会在任何时候进行任何比它需要的更多的排序。

The elements are only ordered as they are dequeued, i.e. removed from the queue using poll(). This is the reason why a PriorityQueue manages to have such good performance, as it is not doing any more sorting than it needs at any time.

如果你想知道如何heaps工作细节我建议这个关于堆的麻省理工学院讲座。

If you want to know how heaps work in detail I recommend this MIT lecture on heaps.

这篇关于在Java中对优先级队列进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！