Heap Sort Algorithm: Step by Step Guide with C++ Code

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It is one of the most efficient sorting algorithms, with a time complexity of O(n*logn) and a space complexity of O(1). In this blog, we will discuss the Heap sort algorithm in detail, along with its implementation in C++.

What is Heap Sort Algorithm?

Heap sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It works by constructing a binary heap from the array of elements to be sorted and then repeatedly extracting the maximum element from the heap and placing it at the end of the sorted array. The process continues until the heap is empty, and the sorted array is obtained.

Explanation of Heap Sort Algorithm in C++

The Heap sort algorithm consists of two main functions, heapify() and heapSort().

Heapify Function

The heapify() function is used to maintain the heap property of a binary tree. The heap property means the root node should be greater than its child nodes. If the heap property is violated, heapify() function is called recursively to fix the heap property.

void heapify(int arr[], int n, int i)
{
    int largest = i;     // Initialize largest as root
    int left = 2 * i + 1;    // left = 2*i + 1
    int right = 2 * i + 2;   // right = 2*i + 2

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i)
    {
        swap(arr[i], arr[largest]); // Swap
        heapify(arr, n, largest);   // Recursively heapify the affected sub-tree
    }
}

Heap Sort Function

The heapSort() function is used to sort the array in ascending order. It starts by building a binary heap from the array. It then repeatedly extracts the maximum element from the heap and places it at the end of the sorted array.

void heapSort(int arr[], int n)
{
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Extract elements from heap one by one
    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
        heapify(arr, i, 0);
    }
}

Step by Step Guide to Implement Heap Sort Algorithm

1. Build a binary heap from the array of elements to be sorted. This can be done in O(n) time complexity.
2. Extract the maximum element from the heap and place it at the end of the sorted array.
3. Repeat step 2 until the heap is empty, and the sorted array is obtained.

C++ Code for Heap Sort Algorithm

Here is the C++ code for Heap Sort Algorithm with detailed explanation:

#include <bits/stdc++.h>
using namespace std;

// Heapify function to maintain heap property
void heapify(int arr[], int n, int i)
{
    int largest = i;     // Initialize largest as root
    int left = 2 * i + 1;    // left = 2*i + 1
    int right = 2 * i + 2;   // right = 2*i + 2

    // If left child is larger than root
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger than largest so far
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If largest is not root
    if (largest != i)
    {
        swap(arr[i], arr[largest]); // Swap
        heapify(arr, n, largest);   // Recursively heapify the affected sub-tree
    }
}

// Main function to perform heap sort
void heapSort(int arr[], int n)
{
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Extract elements from heap one by one
    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
        heapify(arr, i, 0);
    }
}

// Driver code
int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    heapSort(arr, n);

    cout << "Sorted array is: \\n";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
    return 0;
}

Output:

Sorted array is:
5 6 7 11 12 13

Time and Space Complexity of Heap Sort Algorithm

The time complexity of Heap sort algorithm is O(nlogn), and the space complexity is O(1). The time complexity of heapify() function is O(logn), and it is called n times, so the overall time complexity of the algorithm is O(nlogn).

Conclusion

Heap sort is one of the most efficient sorting algorithms with a time complexity of O(n*logn) and a space complexity of O(1). In this blog, we discussed the step by step guide to implement the Heap sort algorithm in C++ along with its time and space complexity analysis.

I hope this blog helped you understand the Heap sort algorithm and its implementation in C++. If you have any questions or suggestions, feel free to leave them in the comments below.