Heap Sort

Heapsort is another very efficient sorting algorithm. The time it runs is O(nlgn), and you cant get better than that.

The data structure used in this sorting algorithm is the Heap. A Binary Tree in which every parent is bigger or equal to his children.

Heaps can be implemented in many different ways, using arrays or Dynamic Structures.

The sub-routines neccessary to maintain a heap:

Note: The following procedures assume that the heap is stored inside an Array.

Parent(I)
Left(I)
Right(I)

These three fundamental procedures will return the parent, the left child or the right child of the I node. They can return the number of the cell in the array in which the value is stored, or a pointer for that node. Depends on how you are implementing the heap.

Heapify(A,I)
// A is either the array that stores the heap and I is the index of the node.
// This recursive procedure assumes that the sub-trees of I are heaps, but A(i) could be smaller than one of the nodes in these sub-trees and fixes the problem.
// The running time of Heapify is O(nlgn)
  l<--Left(I)
  r<--Right(I)
  if l<=Heapsize(A) and A(l)>A(i) then
     largest<--l else
     lasgest<--i
  if r<=Heapsize(A) and A(r)>A(largest) then
     largest<--r
  if largest <> i then
     A(i)<-->A(largest)
     Heapify(A,largest)


Build_Heap(A)
//Takes a regular array and makes a heap out of it by heapifying all the non-leaf nodes.
// The running time of Buildheap is O(nlgn)
 Heapsize(A)<--Length(A)
 for i<--Parent(A(Heapsize(A)) downto 1
      do Heapify(A,i)

And finally, the Heapsort algorithm. First, the Algorithm turns the array to a heap, and then, since the first node is the biggest it replaces it with the last node and decreases the heap size by one. Now the biggest number is in the correct spot, and the process repeats.

Heapsort(A)
// The running time of Heapsort is O(nlgn)
 Build_Heap(A)
 for i<--length(A) downto 2
     do A(1)<-->A(i)
        Heapsize(A)<--Heapsize(A)-1
        Heapify(A,1)


Note: These algorithms can be easily changed if you prefer to implement heaps using dynamic structures.

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).