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. We would discuss about Max-Heap and it will apply for Min-Heap also.

We would 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 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