我阅读了文档以及可以找到的关于PriorityQueue的所有信息,但仍然不明白为什么输出如此奇怪,我的意思是我无法理解添加订单的意义,有人可以解释吗?
PriorityQueue<String> pq = new PriorityQueue<String>(); pq.offer("2"); System.out.println("add 2 : " + pq); pq.offer("4"); System.out.println("add 4 : " + pq); System.out.println(pq.peek() + " "); pq.offer("1"); System.out.println("offer 1 : " + pq); pq.offer("3"); System.out.println("add 3 : " + pq); pq.remove("1"); System.out.println("remove 1 : " + pq);
输出:
add 2 : [2] add 4 : [2, 4] <- why 4 goes there offer 1 : [1, 4, 2] <- why 1 goes first add 3 : [1, 3, 2, 4] <- why reorder remove 1 : [2, 3, 4] <- again
PriorityQueue 仅保证第一个元素最小。
PriorityQueue
甲 二进制堆仅在每个子HEAB(子树)保证根是最小的元素。 堆实际上是一个完整树(或它的数组表示形式)。每当您插入违反条件的元素(小于根)时,都会过滤掉旧根。这是在堆上递归完成的。
这种部分排序允许快速且相对高速缓存有效(具有数组表示)的数据结构,如果您在每个时间点仅需要min元素,则可以使用该结构。