优先级队列中的排序与未排序数据为什么自动排序和排序等待？

我知道最小堆是类使用的结构，因为它的效率很高。在我看来，当将未排序的数据提供给PQ时，会将其分类为堆。优先级队列中的排序与未排序数据为什么自动排序和排序等待？

但是当按照compareTo方法提供元素时，它会在PQ上执行第一个操作后等待将其排序到堆中。

你知道这是为什么吗？我不明白为什么它不像无序数据那样自动排序。

我附上了一个程序，我认为证明了我的问题。

输出：

未排序的数据：

[A，B，d，C，L，F，E，J]

甲

[B，C， d，J，L，F，E]

[1，2，4，3，12，6，5，10]

[2，3，4，10，12，6，5]

排序的数据：

[A，B，C，d，E，F，G ，H]

甲

[B，d，C，H，E，F，G]

[1，2，3，4，5，6，7，8]

[2,4，3,8，5，6，7]

import java.util.PriorityQueue; 

public class Queue2 
{ 
    public static void main(String[] args) 
    { 
     PriorityQueue<String> pQueue = new PriorityQueue<String>(); 

     pQueue.add("A"); 
     pQueue.add("C"); 
     pQueue.add("F"); 
     pQueue.add("B"); 
     pQueue.add("L"); 
     pQueue.add("D"); 
     pQueue.add("E"); 
     pQueue.add("J"); 
     System.out.println(pQueue); 
     System.out.println(pQueue.remove()); 
     System.out.println(pQueue); 

     System.out.println(); 

     PriorityQueue<Integer> pQueue2 = new PriorityQueue<Integer>(); 

     pQueue2.add(1); 
     pQueue2.add(3); 
     pQueue2.add(6); 
     pQueue2.add(2); 
     pQueue2.add(12); 
     pQueue2.add(4); 
     pQueue2.add(5); 
     pQueue2.add(10); 
     System.out.println(pQueue2); 
     System.out.println(pQueue2.remove()); 
     System.out.println(pQueue2); 

     System.out.println(); 

     PriorityQueue<String> pQueue3 = new PriorityQueue<String>(); 

     pQueue3.add("A"); 
     pQueue3.add("B"); 
     pQueue3.add("C"); 
     pQueue3.add("D"); 
     pQueue3.add("E"); 
     pQueue3.add("F"); 
     pQueue3.add("G"); 
     pQueue3.add("H"); 
     System.out.println(pQueue3); 
     System.out.println(pQueue3.remove()); 
     System.out.println(pQueue3); 

     System.out.println(); 

     PriorityQueue<Integer> pQueue4 = new PriorityQueue<Integer>(); 

     pQueue4.add(1); 
     pQueue4.add(2); 
     pQueue4.add(3); 
     pQueue4.add(4); 
     pQueue4.add(5); 
     pQueue4.add(6); 
     pQueue4.add(7); 
     pQueue4.add(8); 
     System.out.println(pQueue4); 
     System.out.println(pQueue4.remove()); 
     System.out.println(pQueue4); 

    } 
}

来源

2013-05-28 user2428874

所以你知道有队列下方的（二进制）堆，是吗？堆应该坚持两个properties：

的形状属性：树是完全二叉树;也就是说，除了可能最后一个（最深）的树以外，树的所有级别都被完全填充，并且如果树的最后一级未完成，则该级别的节点将从左到右填充。
heap属性：根据为数据结构定义的比较谓词，每个节点大于或等于其每个子节点。

那么如何插入元素？做一个BFS直到你找到一个空白点（把该元素放在那个点上），或者找到另一个比当前元素大的元素（用新元素替换那个元素并继续使用更大的元素）。

让我们来看看你的两个例子。我将逐级写入树，因此[A][BC][D---]表示以A作为根的树，B和CA和D的子节点B的子节点。

我们来看第一个例子：[A, C, F, B, L, D, E, J]。这是堆是如何增长的：

[A] 
[A][C-] 
[A][CF] 
[A][BF][C---] 
[A][BF][CL--] 
[A][BD][CLF-] 
[A][BD][CLFE] 
[A][BD][CLFE][J-------]

现在看看你的排序例如：[A, B, C, D, E, F, G, H]。这是如何堆成长：

[A] 
[A][B-] 
[A][BC] 
[A][BC][D---] 
[A][BC][DE--] 
[A][BC][DEF-] 
[A][BC][DEFG] 
[A][BC][DEFG][H-------]

所以确实，底层数组包含排序顺序的所有元素。

那么，为什么这个顺序在第一个元素被删除时失真？为了满足堆的两个属性，空点重复填充该点的最小子。

让我们消除A（我标志着由*空点）后，看看最后一个例子：

[*][BC][DEFG][H-------] 
[B][*C][DEFG][H-------] 
[B][DC][*EFG][H-------] 
[B][DC][HEFG]

这也相当于你给输出。

来源

2013-05-28 14:54:24

所以我认为你说的是有序的信息符合形状和堆属性，因此是一个min二进制堆，不需要改变。只有当物品被移除时才会更改。而无序数据需要在堆被更改之前排入堆中。因此，我的问题将是一个糟糕的问题，因为排序后的数据堆积如山。 – user2428874

@ user2428874好吧，我不认为这是一个坏问题，但其余的就是这样。你打印的是底层数组，它确实代表了二进制最小堆。 –

感谢您的帮助。我觉得有点傻，但你的解释确实有帮助。我无法提前建立连接。再次感谢！ – user2428874

从PriorityQueue

这个队列的头中的文档是相对于指定的排序的最小元素。如果多个元素的最小值相关联，则头是其中一个元素 - 关系被任意破坏。队列检索操作轮询，删除，查看和元素访问队列头部的元素。

而且

此类及其迭代器实现Collection和Iterator接口的所有可选方法。 方法iterator（）中提供的Iterator不保证以任何特定顺序遍历优先级队列的元素。如果您需要有序遍历，请考虑使用Arrays.sort（pq.toArray（））。

这就是为什么当你打印队列（用的System.out）在内部使用和迭代器因此没有有序输出的guarenty ......但如果你使用poll()多次，你一定会看到的对象返回在这两种情况下有序方式

来源

2013-05-28 14:58:28

优先级队列中的排序与未排序数据为什么自动排序和排序等待？

回答

相关问题