Heap Sort array

Question

Who can explain to me exactly how it works next sequence of code.

 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

As @DeltaLima mentioned, from PriorityQueue documentation -

An unbounded priority queue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.

As you are using Integers, which have natural ordering defined, it works out of the box.

The only thing I am not sure about is if this is the real heap sort - http://en.wikipedia.org/wiki/Heapsort

I hope that helps.

Answer 2

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

This line creates a priority queue of Integers. A priority queue stores a "sorted" list of items (in your case Integers).

When you add an int to pQueue ,it is places the value in the correct position.

E.g if I add numbers 1, 10 and 5 in this order to a priority Queue, something like this will happen:

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

notice how 5 gets placed between 1 and 10.

When you call pQueue.poll(); the first element of pQueue is returned which is guaranteed to be the smallest value inside the queue. (The value is removed from the queue during this process).

Repeated calls would return the numbers in the example above in the order 1 , 5, 10.

Due to this your array gets sorted.