Heap Sort is another sorting algorithm that is comparison based and is part of the selection sort group of algorithms. In terms of performance, it has the same O(n * log n) time complexity and is close to being as efficient as the Quick Sort and Merge Sort, however, it is a bit slower. It is also like the Insertion Sort in that sorting is done in place (a constant space of O(1)), so no additional space is needed in order to sort. Unlike Merge Sort, it is not stable.
When to use Heap Sort
The C Version of Heap Sort
The C++ Version of Heap Sort
The algorithm is as follows:
HEAPSORT(A), where A is an array
1. BUILDHEAP(A)
2. for i = length[A], i >= 0, decrement i
3. do exchange A[1] A[i]
4. heapsize[A] heapsize[A] 1
5. HEAPIFY(A, 1)
More in depth:
1. Start by building a heap
2. Once the heap is constructed, the element in the first position of the array will be the maximum and can be swapped into its correct position. That swap disrupts the heap, but it can be rebuilt by looking at a small portion of the elements in the array using the “heapify” procedure.
The heapsort algorithm starts by using BUILD–HEAP to build a heap on the input array A[1 . . n], where n = length[A]. Since the maximum element of the array is stored at the root A[1], it can be put into its correct final position by exchanging it with A[n]. If node n is now “discarded” from the heap (by decrementing heapsize[A]), it is evident that A[1 . . (n – 1)] can be easily made into a heap. The children of the root remain heaps, but the new root element may violate the heap property. In order to restore the heap property, one call to HEAPIFY(A, 1) leaves a heap in A[1 . . (n – 1)]. The heapsort algorithm then repeats this process for the heap of size n – 1 down to a heap of size 2.
The runtime for Heapsort is O(n * log n). BuildHeap(A) has O(n) runtime time, and the Heapify(A,1) process is logarithmic, so O(log n), and combined produces the O(n * log n) runtime. For the best, average, and worst cases, Heap Sort guarantees O(n * log n) performance. Again, while it is slower than both Quick Sort and Merge Sort, Heap Sort guarantees in the worst case, logarithmic time.
There are a few parts to implementing this algorithm:
The heap
 The heap is essentially an array that is represented/viewed as a binary tree structure, however, this binary tree structure is partially unsorted.
 Remember that a heap is another way to represent a priority queue
 A heap needs to be made in order to implement Heap Sort
 The heap can be built recursively using this method

BUILDHEAP(A)
1. heapsize[A] < length[A]
2. for i < length[A]/2 downto 1
3. do HEAPIFY(A, i)

The Sorting
The overall sorting method that heapsort does occurs in the Heapify method. Heapify is used to restore the heap property of the array. This method can be written using the following pseudocode:
HEAPIFY(A, i)
1 l < LEFT(i)
2 r < RIGHT(i)
3 largest = i
4 if l <= heapsize[A] and A[l] > A[i]
5 then largest < l
6 else largest < i
7 if r <= heapsize[A] and A[r] > A[largest]
8 then largest < r
9 if largest != i
10 then SWAP A[i] < A[largest]
11 HEAPIFY(A,largest)
Implementation in C#
class Program { static void Main(string[] args) { int[] arr = { 10, 64, 7, 52, 32, 18, 2, 48}; HeapSort hs = new HeapSort(); hs.PerformHeapSort(arr); Console.ReadLine(); } } class HeapSort { private int heapSize; private void BuildHeap(int[] arr) { heapSize = arr.Length1; for (int i = heapSize/2; i >= 0; i) { Heapify(arr, i); } } private void Swap(int[] arr, int x, int y)//function to swap elements { int temp = arr[x]; arr[x] = arr[y]; arr[y] = temp; } private void Heapify(int[] arr, int index) { int left = 2 * index; int right = 2 * index + 1; int largest = index; if (left <= heapSize && arr[left] > arr[index]) { largest = left; } if (right <= heapSize && arr[right] > arr[largest]) { largest = right; } if (largest != index) { Swap(arr, index, largest); Heapify(arr, largest); } } public void PerformHeapSort(int[] arr) { BuildHeap(arr); for (int i = arr.Length1; i >= 0; i) { Swap(arr, 0, i); heapSize; Heapify(arr, 0); } DisplayArray(arr); } private void DisplayArray(int[] arr) { for (int i = 0; i < arr.Length; i++) { Console.Write("[{0}]", arr[i]); } } }
Pingback: The Heap Data Structure (C++, Java, C#)  Bits and Pieces of Code