Heap Sort in java

The sorting problem
Input: Array of numbers , unsorted. Eg.

Output : Same numbers sorted in some order, say increasing order. Eg.

Heap sort Algorithm
This algorithm assumes understanding of heap - Heap - Introduction. Also, it also uses ExtractMin from Heap.

Algorithm
The essence of heap sort (in-place) is this:

1. Convert the array to be sorted into a heap. (see BuildHeap, it uses O(n) time)
2. Build the sorted array back to front by repeatedly
   1. removing the minimum value in the heap (the value at position 1),
   2. putting that value into the sorted array, and
   3. rebuilding the heap with one fewer element.
3. Use the same array for the heap and the sorted array.

Pseudocode using Min-heap (sorts in descending order)

Heap-Sort(int[] arr) 
{
  Build-Heap(arr)
  for i = arr.length downto 2
  {
    swap arr[0] and arr[i]
    heap-size[arr] = heap-size[arr] - 1
    BubbleDown(arr,heap-size)
  }
}

Example

Consider the array to be sorted as  - 4,4,8,9,4,12,9,11,13

So we get heap as :

Now, currently i = arr.length -1, So we swap arr[i] and arr[0] i.e. 13 and 4.

Once this is done we can see 4 is at last position. So considering the array to be sorted in descending order, we are fine as it should be the min element of the heap and is it end. So we just remove this element from the heap but not from array. So, we have to decrease heap size:

Now the last element of heap is 11, and not 4. But array still has all the elements.

Now we can see that the heap property (min) is destroyed, i.e. parent<=child. So 13 at root node violates it. So we have to bubble down (or sift down or heapify).

But still the heap property is not restored, as 13 is larger than both 9 and 4. So we bubble it down again.

Now, we can see that the heap property is restored, and hence we now swap arr[0] and arr[length-2]. Where length-2 = heap size and repeat the same procedure.

Time complexity
Time complexity for building the heap is O(n). Also, for bubbling down time complexity is O(log n). Bubbling down is called per node, hence the time complexity is O(n log n). So total time complexity is O(n) + O( n log n) i.e. O(n log n)

Java Code :
To come soon.