Heap Sort Algorithm in C++

In this post, we are going to understand Heap sort which is similar to the selection sort algorithm for sorting data.

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort an array. A binary heap is a complete binary tree that satisfies the "heap property," which states that the value of each node is greater than or equal to the values of its children (for a max-heap) or less than or equal to the values of its children (for a min-heap).

The basic steps of the heap sort algorithm in C++:

Step 1. Build a max-heap from the input array.

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

Step 2: Swap the root (maximum value) of the heap with the last element of the array. This moves the maximum value to the end of the array. Then, call the heapify function on the remaining elements, except the last one, to maintain the heap property.

void heap_sort(int arr[], int n) {
    build_max_heap(arr, n);

    for (int i = n-1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

Step 3: The heapify function is used to maintain the heap property. It compares the value of the node with its children and if the value of the node is less than the value of its children, it swaps the values of the node with the largest value among its children.

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

Complete C++ Program for Heap Sort.

//C++ Example for Heap Sort Algorithm
#include<iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}
//function to build max heap
void build_max_heap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}
//heap sort function
void heap_sort(int arr[], int n) {
    build_max_heap(arr, n);

    for (int i = n-1; i >= 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

int main()
{
    int arr[] = {3, 8, 1, 4, 2, 11};
    int n = sizeof(arr)/sizeof(arr[0]);

    heap_sort(arr, n);

    for(int i = 0; i < n; i++)
       cout<<arr[i]<<" ";

    return 0;   
}

Output:

1 2 3 4 8 11

• Time Complexity: O(n log n)
• Space Complexity: O(1)

Heap sort is better than bubble sort and selection sort but not better than insertion sort.