Heap Data structure | Heap Sort in C++

The Heap data structure is an array that can be viewed as a (almost) complete Binary Tree. Each node in the tree corresponds to an element of the array A[].

The root of the tree is A[0]. And given the index i of an element, we could find, 
Parent (i):
 return (A[(i-1)/2])

Left-Child (i):
 return (A[2*i + 1])

Right-Child (i):
 return (A[2*i + 2])

There are two types of Binary heaps:

1. Max-Heap
2. Min-Heap

Each kind of heap satisfies the heap-property. In a max-heap, the max-heap property is:

A[Parent(i)] >= A[i]

Similarly in a min-heap, the min-heap property is:

A[Parent(i)] <= A[i]

Now since, Min-Heap and Max-Heap are exactly the same with just different max and min property. Whatever we’ll discuss about Max-Heap, it will also apply for Min-Heap.

We will now discuss the following major methods (procedures) and algorithm:

• Max-Heapify procedure: running time O(logn)
• Build-Max-Heap procedure: running time O(n)
• Heapsort algorithm: running time O(nlogn)

Max-Heapify

It is the key procedure to maintain the max-heap property. It inputs an array (A) and an index i of the array A and is used to build the max-heap.
Max-Heapify procedure takes O(logn) time.

Pseudocode

Max-Heapify (A, i)
  l = Left-Child(i)
  r = Right-Child(i)
  if (l < A.size() && A[l] > A[i])
    largest = l
  else
    largest = i
  if (r < A.size() && A[r] > A[i])
    largest = r
  // Since there's a change in heap,
  // we need to again assure heap-property
  if largest != i
    exchange (A[i], A[largest])
    Max-Heapify (A, largest)

Build-Max-Heap

This method outputs a max-heap from an unordered input array and runs in O(n) time.

Pseudocode

Build-Max-Heap (A)
  heap_size(A) = A.size()
  for i = length(A/2) to i
    Max-Heapify (A, i) 

Heapsort

The Heapsort algorithm uses Heap data structure to sort an array in O(nlogn) time complexity. It starts by calling Build-Max-Heap to build a max-heap of the input array A[0..n-1]. It iteratively removes the max element (or the root element, A[0]) from the heap and places it at its correct position ie A[n-1]. And then decreases the heap-size (n) by 1 ie. n = n-1. It doesn’t end there, since children of root maintain the heap-property but root element (previously one of the smaller (root’s children) elements) may violate the root property. So, we need to restore the max-heap-property by calling Max-Heapify(A, n).

Note: Since, in a Binary Max-heap, the root element (ie A[0]) will always be the largest element, we can put the root element to its correct position (A[n-1]) after each iteration.

Pseudocode

Heapsort (A)
  Build-Max-Heap (A)
  n = A.size()

  for i = n-1 to 0
    exchange(A[0], A[i])
    n = n-1
    Max-Heapify (A, n)

The Heapsort procedure takes time O(nlogn), since the call to Build-Max-Heap take O(n) time and each of the n calls to Max-Heapify takes O(logn) time.

Code Implementation

//
//  main.cpp
//  Heapsort
//
//  Created by Himanshu on 25/09/21.
//

#include <iostream>
using namespace std;

void printArray (int arr[], int n) {
    for (int i=0; i<n; i++) {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}

void MaxHeapify(int arr[], int i, int heapSize) {
    int l, r, large;
    l = 2*i + 1;
    r = 2*i + 2;
    if (l < heapSize && arr[l] > arr[i]) {
        large = l;
    } else {
        large = i;
    }
    
    if (r < heapSize && arr[r] > arr[large]) {
        large = r;
    }
    
    //Assuring heap property
    if (large != i) {
        swap (arr[i], arr[large]);
        MaxHeapify(arr, large, heapSize);
    }
}

void BuildHeap(int arr[], int n) {
    int k = (n/2)-1;
    for (int i=k; i>=0; i--) {
        MaxHeapify(arr, i, n);
    }
}

void Heapsort (int arr[], int n) {
    BuildHeap(arr, n);
    int j = 1, N = n;
    
    for (int i=n-1; i>=0; i--) {
        swap(arr[0], arr[i]);
        n--;
        
        MaxHeapify(arr, 0, n);
        printf("Array after %d Max-Heapify\n", j++);
        printArray(arr, N);
    }
}

int main() {
    int arr[] = {8, 3, 9, 2, 16, 10, 14, 7, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout<<"Initial Array:"<<endl;
    printArray(arr, n);
    cout<<endl;
    
    Heapsort(arr, n);
    
    cout<<endl<<"Array after Heapsort:"<<endl;
    printArray(arr, n);
    
    return 0;
}

Output

Initial Array:
8 3 9 2 16 10 14 7 4 

Array after 1 Max-Heapify
14 8 10 7 3 4 9 2 16 
Array after 2 Max-Heapify
10 8 9 7 3 4 2 14 16 
Array after 3 Max-Heapify
9 8 4 7 3 2 10 14 16 
Array after 4 Max-Heapify
8 7 4 2 3 9 10 14 16 
Array after 5 Max-Heapify
7 3 4 2 8 9 10 14 16 
Array after 6 Max-Heapify
4 3 2 7 8 9 10 14 16 
Array after 7 Max-Heapify
3 2 4 7 8 9 10 14 16 
Array after 8 Max-Heapify
2 3 4 7 8 9 10 14 16 
Array after 9 Max-Heapify
2 3 4 7 8 9 10 14 16 

Array after Heapsort:
2 3 4 7 8 9 10 14 16 

Notice, how after each Max-Heapify operation, largest element in the remaining array is put at its correct position.
Here’s a working example: Ideone