Heap Sort
Heapsort is a comparisonbased sorting algorithm. Heapsort is part of the selection sort family; it improves on the basic selection sort by using a logarithmictime priority queue rather than a lineartime search. Although somewhat slower in practice on most machines than a wellimplemented quicksort, it has the advantage of a more favorable worstcase O(n log n) runtime. Heapsort is an inplace algorithm, but it is not a stable sort. It was invented by J. W. J. Williams in 1964.
A run of the heapsort algorithm sorting an array of randomly permuted values. In the first stage of the algorithm the array elements are reordered to satisfy the heap property. Before the actual sorting takes place, the heap tree structure is shown briefly for illustration.


Class  Sorting algorithm 

Data structure  Array 
Worst case performance  
Best case performance  ^{[1]} 
Average case performance  
Worst case space complexity  auxiliary 
The heapsort algorithm can be divided into two parts.
In the first step, a heap is built out of the data. The heap is often placed in an array with the layout of a complete binary tree. The complete binary tree maps the binary tree structure into the array indices; each array index represents a node; the index of the node’s parent, left child branch, or right child branch are simple expressions. For a zerobased array, the root node is stored at index 0; if i
is the index of the current node, then
iParent = floor((i1) / 2) iLeftChild = 2*i + 1 iRightChild = 2*i + 2
In the second step, a sorted array is created by repeatedly removing the largest element from the heap (the root of the heap), and inserting it into the array. The heap is updated after each removal to maintain the heap. Once all objects have been removed from the heap, the result is a sorted array.
Heapsort can be performed in place. The array can be split into two parts, the sorted array and the heap. The storage of heaps as arrays is diagrammed here. The heap’s invariant is preserved after each extraction, so the only cost is that of extraction.
Example
Let { 6, 5, 3, 1, 8, 7, 2, 4 } be the list that we want to sort from the smallest to the largest. (NOTE, for ‘Building the Heap’ step: Larger nodes don’t stay below smaller node parents. They are swapped with parents, and then recursively checked if another swap is needed, to keep larger numbers above smaller numbers on the heap binary tree.)
1. Build the heap
Heap  newly added element  swap elements 

nil  6  
6  5  
6, 5  3  
6, 5, 3  1  
6, 5, 3, 1  8  
6, 5, 3, 1, 8  5, 8  
6, 8, 3, 1, 5  6, 8  
8, 6, 3, 1, 5  7  
8, 6, 3, 1, 5, 7  3, 7  
8, 6, 7, 1, 5, 3  2  
8, 6, 7, 1, 5, 3, 2  4  
8, 6, 7, 1, 5, 3, 2, 4  1, 4  
8, 6, 7, 4, 5, 3, 2, 1 
2. Sorting.
Heap  swap elements  delete element  sorted array  details 

8, 6, 7, 4, 5, 3, 2, 1  8, 1  swap 8 and 1 in order to delete 8 from heap  
1, 6, 7, 4, 5, 3, 2, 8  8  delete 8 from heap and add to sorted array  
1, 6, 7, 4, 5, 3, 2  1, 7  8  swap 1 and 7 as they are not in order in the heap  
7, 6, 1, 4, 5, 3, 2  1, 3  8  swap 1 and 3 as they are not in order in the heap  
7, 6, 3, 4, 5, 1, 2  7, 2  8  swap 7 and 2 in order to delete 7 from heap  
2, 6, 3, 4, 5, 1, 7  7  8  delete 7 from heap and add to sorted array  
2, 6, 3, 4, 5, 1  2, 6  7, 8  swap 2 and 6 as they are not in order in the heap  
6, 2, 3, 4, 5, 1  2, 5  7, 8  swap 2 and 5 as they are not in order in the heap  
6, 5, 3, 4, 2, 1  6, 1  7, 8  swap 6 and 1 in order to delete 6 from heap  
1, 5, 3, 4, 2, 6  6  7, 8  delete 6 from heap and add to sorted array  
1, 5, 3, 4, 2  1, 5  6, 7, 8  swap 1 and 5 as they are not in order in the heap  
5, 1, 3, 4, 2  1, 4  6, 7, 8  swap 1 and 4 as they are not in order in the heap  
5, 4, 3, 1, 2  5, 2  6, 7, 8  swap 5 and 2 in order to delete 5 from heap  
2, 4, 3, 1, 5  5  6, 7, 8  delete 5 from heap and add to sorted array  
2, 4, 3, 1  2, 4  5, 6, 7, 8  swap 2 and 4 as they are not in order in the heap  
4, 2, 3, 1  4, 1  5, 6, 7, 8  swap 4 and 1 in order to delete 4 from heap  
1, 2, 3, 4  4  5, 6, 7, 8  delete 4 from heap and add to sorted array  
1, 2, 3  1, 3  4, 5, 6, 7, 8  swap 1 and 3 as they are not in order in the heap  
3, 2, 1  3, 1  4, 5, 6, 7, 8  swap 3 and 1 in order to delete 3 from heap  
1, 2, 3  3  4, 5, 6, 7, 8  delete 3 from heap and add to sorted array  
1, 2  1, 2  3, 4, 5, 6, 7, 8  swap 1 and 2 as they are not in order in the heap  
2, 1  2, 1  3, 4, 5, 6, 7, 8  swap 2 and 1 in order to delete 2 from heap  
1, 2  2  3, 4, 5, 6, 7, 8  delete 2 from heap and add to sorted array  
1  1  2, 3, 4, 5, 6, 7, 8  delete 1 from heap and add to sorted array  
1, 2, 3, 4, 5, 6, 7, 8  completed 