**Heapsort** is a much more popular and efficient version of selection sort. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a heap, a special type of binary tree.

Once the data list has been made into a heap, the root node is guaranteed to be the largest (or smallest) element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root.

A heap is represented as an left-complete binary tree. This means that all the levels of the tree are full except the bottom-most level, which is filled from left to right. The HeapSort algorithm will consist of** two major parts**. First building a heap, and then extracting the maximum elements from the heap, one by one. We will see how to use Heapify to help us do both of these.

**Build max-heap:**

Here is the code. Since we will work with the entire array, the parametermfor Heapify, which indicates

the current heap size will be equal to **n**, the size of array **A**, in all the calls.

1 2 3 4 5 |
BuildHeap(int n, array A[1..n]) { // build heap from A[1..n] for i = n/2 downto 1 { Heapify(A, i, n) } } |

**Heap sort Algorithm:**

We can now give the **HeapSort** algorithm. The idea is that we need to repeatedly extract the maximum item from the heap. As we mentioned earlier, this element is at the root of the heap. But once we remove it we are left with a hole in the tree. To fix this we will replace it with the last leaf in the tree (the one at position A[m]). But now the heap order will very likely be destroyed. So we will just apply Heapify to the root to fix everything back up.

1 2 3 4 5 6 7 8 9 10 |
HeapSort(int n, array A[1..n]) { // sort A[1..n] BuildHeap(n, A) // build the heap m = n // initially heap contains all while (m >= 2) { swap A[1] with A[m] // extract the m-th largest m = m-1 // unlink A[m] from heap Heapify(A, 1, m) // fix things up } } |

### Example:

Let’s look at In the example below, initially there is an unsorted array Arr having 6 elements and then max-heap will be built.

After building max-heap, the elements in the tree will be swap like below:

**Step 1:** 8 is swapped with 5.

**Step 2:** 8 is disconnected from heap as 8 is in correct position now and.

**Step 3:** Max-heap is created and 7 is swapped with 3.

**Step 4:** 7 is disconnected from heap.

**Step 5:** Max heap is created and 5 is swapped with 1.

**Step 6:** 5 is disconnected from heap.

**Step 7:** Max heap is created and 4 is swapped with 3.

**Step 8:** 4 is disconnected from heap.

**Step 9:** Max heap is created and 3 is swapped with 1.

**Step 10:** 3 is disconnected.

As show in the above diagram, we start by heapifying the lowest smallest trees and gradually move up until we reach the root element.

After all the steps, we will get a final sorted array list:

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
#include <iostream> using namespace std; // To max_heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap void max_heapify(int arr[], int n, int i) { int largest = i; // Initialize largest as root int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // If left child is larger than root if (l < n && arr[l] > arr[largest]) largest = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) largest = r; // If largest is not root if (largest != i) { swap(arr[i], arr[largest]); // Recursively max_heapify the affected sub-tree max_heapify(arr, n, largest); } } // simple function to do heap sort void heapSort(int arr[], int n) { // Build heap (rearrange array) for (int i = n / 2 - 1; i >= 0; i--) max_heapify(arr, n, i); // One by one extract an element from heap for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr[0], arr[i]); // call max heapify on the reduced heap max_heapify(arr, i, 0); } } /* A utility function to print array of size n */ void printArray(int arr[], int n) { for (int i = 0; i < n; ++i) cout << arr[i] << " "; cout << "\n"; } // Main function int main() { int arr[100]; int i; int n; cout<<"How many elements you want to enter?\n"; cin>>n; cout<<"Enter the "<<n<<" elements:\n"; for(i = 0; i < n; i++) { cin>>arr[i]; } i = sizeof(arr)/sizeof(arr[0]); heapSort(arr, n); cout << "Sorted array:\n"; printArray(arr, n); } |

When you run the program, the output will be following:

1 2 3 4 5 6 7 8 9 10 |
How many elements you want to enter? 5 Enter the 5 elements: 12 8 32 4 1 Sorted array: 1 4 8 12 32 |

Heap sort is finding the next largest element takes **O(log n)** time for all cases (best case, average case and worst case), instead of O(n) for a linear scan as in simple selection sort. This allows Heapsort to run in O(n log n) time, and this is also the worst case complexity.