Heap Sort

Heap sort doesn’t use any special algorithm to sort the array, it just take advantage of heap property that maximum element will always be on the top. We achieve the sorting as follows:

• • • 1. Exchange the root’s key with the last key K of the heap.
      2. Decrease the heap’s size by 1.
      3. “maxHeapify()” the 0^th node by sifting its key ‘K’ down the tree until it satisfy the heap condition.

Java code for Heap sort

public void heapSort(int[] heapArray) {
		builMaxHeap(heapArray, heapArray.length);
		int heapSize = heapArray.length;
		for (int i = heapSize - 1; i >= 1; i--) {
			int temp = heapArray[0];    //remove the first element
			heapArray[0] = heapArray[i];// top is always the largest
			heapArray[i] = temp;
			heapSize--;                 // top at its right position
			maxHeapify(heapArray,0,heapSize);// top element may violate heap
                                                         //property
		}
	}
Output
--------
Before Sort: [1, 8, 9, 2, 10, 14, 3, 4, 7, 16]
After Sort:  [1, 2, 3, 4, 7, 8, 9, 10, 14, 16]

Efficiency of heapSort()
The heapSort() algorithm starts by using buildMaxHeap() to build a max-heap
on the input array A[0…n-1] which takes O(n) time, and then calling maxHeapify() (n-2) times which takes O(logn) time. Therefore we can say that The heapSort() procedure takes O(nlogn) time.
The HeapSort time efficiency is same as MergeSort. Unlike MergeSort, HeapSort is in place sorting i.e. it doesn’t require extra space. Timing experiments on random files shows that HeapSort runs more slowly than Quicksort but can be competitive with MergeSort.

Here one important question arise that why the maxHeapify() method in heapSort() takes O(logn) why not O(n) time as it takes in buildMaxHeap()?
The answer lies in the call of maxHeapify() inside heapSort(). We call maxHeapify(0) n-2 times. At each call the node of the level 0 will travel the distance is proportional to the height(logn) of the tree. The height of the tree stays constant until you have removed the first half of the nodes.
Next  ↠Heap as Priority Queue ↠↠

References:

• • • Introduction To Algorithm – CLRS.
    • The Design and analysis of Algorithms – Anany Levitin
    • Data Structure & Algorithms In Java – Robert Lafore
    • Beginning Algorithms – Simon Harris and James Ross
    • http://stackoverflow.com/questions/9755721/build-heap-complexity