Heap Sort (idea)

In computer science, a Heap is a tree structure in which the root contains the largest (or smallest) element.(a Heap can be also represented as an Array).

The Heap Sort algorithm is an improved version of straight selection sort. The straight selection sort algorithm scans unsorted elements in a list and selects the smallest element. Finding the smallest element among n elements requires n – 1 comparisons, hence selection sort makes it very slow.

Heap Sort Algorithm also selects an element from an unsorted portion of the list, but in this case, it selects the largest element (or smallest). Because the structure is a heap (with a tree representation), scanning the whole list to locate the largest element is not necessary. An operation called “reheaping” or moving the largest element to the root of the tree by following tree branches replaces scanning, this ability makes the heap sort much faster than the straight selection sort.

A walk through the following example will help:
Lets sort the following array: 32 78 56 8 23 45

78 32 56 8 23 45 --- Heap in array representation, has the following logical structure:

                       78
                      /   \
                     /     \
                   56      32
                   / \     / \
                  /   \   /   \
                45    8  23   19

After pass 1 and reheap:
56 32 45 8 23 | 78 --- Heap | Sorted
After pass 2 and reheap:
45 32 23 8| 56 78 --- Heap | Sorted
After pass 3 and reheap:
32 8 23 |45 56 78 --- Heap | Sorted
After pass 4 and reheap:
23 8 |32 45 56 78 --- Heap | Sorted
After pass 5 and reheap:
8 | 23 32 45 56 78 --- Heap | Sorted
After pass 6 and reheap:
| 8 23 32 45 56 78 --- Sorted

The Heap Sort algorithm in pseudo code:

	Create heap
	1 walker = 1
	2 loop (walker <= last)
		1 reheapUp( heap, walker)
		2 walker = walker +1
	 Heap created, sort it. 
	3 sorted = last
	4 loop (sorted > 0)
		1 exchange (heap, 0, sorted)
		2 sorted = sorted –1
		3 reheapDown (heap, 0, sorted)
	5 return

end heapSort

The algorithm uses reheapUp (Heap operation) to turn the array into a heap. Then it sorts the array by exchanging the element at the top of the heap with the element at the end of the heap, and rebuilding the heap (using reheapDown).

Heap sort has O(nlog₂n) efficiency compared to O(n²) efficiency of the straight selection sort, using Big-oh Notation (Big-O).