java - 堆排序数组

Question

谁能向我解释下一个代码序列是如何工作的。

 PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>();       
 for (int w : x) {
     pQueue.add(w);
 }
 for (int k = 0; k < x.length; k++) {
     x[k] = pQueue.poll();
 }

 // Print the array
 System.out.println("\nHere is the sorted array with HeapSort:");
 for (int w : x) {
     System.out.print(w + "  ");   
 }

Answer 1

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

此行创建一个整数优先级队列。优先级队列存储项目的“排序”列表（在您的情况下为整数）。

当您将 int 添加到 pQueue 时，它​​会将值放置在正确的位置。

例如，如果我按此顺序将数字 1、10 和 5 添加到优先级队列中，则会发生以下情况：

pqueue = {}          //empty at start
pqueue = {1}         //1 added
pqueue = {1->10}     //10 added
pqueue = {1->5->10} // 5 added

注意 5 是如何放在 1 和 10 之间的。

当您调用pQueue.poll(); pQueue 的第一个元素时，它保证是队列中的最小值。（在此过程中，值将从队列中删除）。

重复调用将按 1、5、10 的顺序返回上例中的数字。

因此，您的数组得到排序。

Answer 2

正如@DeltaLima 提到的，来自PriorityQueue 文档-

基于优先级堆的无界优先级队列。优先级队列的元素根据它们的自然顺序进行排序，或者由队列构建时提供的 Comparator 排序，具体取决于使用的构造函数。

当您使用定义了自然顺序的整数时，它可以开箱即用。

我唯一不确定的是这是否是真正的堆排序 - http://en.wikipedia.org/wiki/Heapsort

我希望这会有所帮助。