How To Do Heap Sort in C++

Heap Sort is an efficient, comparison-based sorting algorithm that uses a binary heap data structure to sort elements in place. It offers a guaranteed time complexity of O(n log n) in all cases, making it reliable for large datasets. In this blog post, we’ll explain how Heap Sort works, provide a C++ implementation, and walk through the sorting process step by step. We’ll also highlight the advantages and limitations of Heap Sort. For more details on Heap sort, go to the article How to do Heap Sort in Python.

---

What is Heap Sort?

Heap Sort is a comparison-based algorithm that builds a binary heap from the input array. A binary heap is a complete binary tree where each parent node is greater than (max-heap) or less than (min-heap) its child nodes.

In Heap Sort, we:

1. Build a max heap from the input data.
2. Swap the root of the heap (the largest element) with the last element of the array.
3. Reheapify the remaining heap to maintain the heap property.
4. Repeat the process until all elements are sorted.

---

How Heap Sort Works

1. Build a max heap: First, the input array is transformed into a max heap.
2. Swap and heapify: Swap the largest element (root) with the last element, reduce the heap size by 1, and reheapify.
3. Repeat: Continue this process until the heap size is reduced to 1.

Time Complexity:

• Best Case: O(n log n)
• Worst Case: O(n log n)
• Average Case: O(n log n)

Space Complexity:

• O(1): Heap Sort is an in-place sorting algorithm.

---

Heap Sort Pseudocode

Here’s the pseudocode for Heap Sort:

HeapSort(array, n):
    BuildMaxHeap(array, n)

    for i = n - 1 down to 1:
        swap(array[0], array[i])
        MaxHeapify(array, 0, i)

BuildMaxHeap(array, n):
    for i = n // 2 - 1 down to 0:
        MaxHeapify(array, i, n)

MaxHeapify(array, i, n):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and array[left] > array[largest]:
        largest = left
    if right < n and array[right] > array[largest]:
        largest = right
    if largest != i:
        swap(array[i], array[largest])
        MaxHeapify(array, largest, n)

---

Heap Sort Algorithm in C++ (Code Example)

Here’s a C++ implementation of Heap Sort:

#include <iostream>
using namespace std;

// Function to heapify a subtree rooted at node i, where n is the size of the heap
void heapify(int arr[], int n, int i) {
    int largest = i;       // Initialize the largest as root
    int left = 2 * i + 1;  // Left child
    int right = 2 * i + 2; // Right child

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

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

    // If the largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]);  // Swap root and the largest child

        // Recursively heapify the affected subtree
        heapify(arr, n, largest);
    }
}

// Function to perform heap sort
void heapSort(int arr[], int n) {
    // Step 1: Build a max heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // Step 2: Extract elements one by one from the heap
    for (int i = n - 1; i >= 0; i--) {
        swap(arr[0], arr[i]);  // Move the current root to the end
        heapify(arr, i, 0);    // Call heapify on the reduced heap
    }
}

// Utility function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

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

    cout << "Original array: ";
    printArray(arr, n);

    heapSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

Output:

Original array: 12 11 13 5 6 7 
Sorted array: 5 6 7 11 12 13

---

Step-by-Step Walkthrough of Heap Sort

Let’s walk through how Heap Sort works for the array [12, 11, 13, 5, 6, 7].

Step 1: Build the Max Heap

We start by building a max heap from the input array. The heap property ensures that the root of the tree is the largest element.

Array after building the max heap:

[13, 11, 12, 5, 6, 7]

Step 2: Extract the Maximum Element

Now, we repeatedly swap the root of the heap (the largest element) with the last element and reduce the heap size. Then, we heapify the root to maintain the max heap property.

Swap 13 and 7, then heapify:

[12, 11, 7, 5, 6, 13]

Swap 12 and 6, then heapify:

[11, 6, 7, 5, 12, 13]

Swap 11 and 5, then heapify:

[7, 6, 5, 11, 12, 13]

Swap 7 and 5, then heapify:

[6, 5, 7, 11, 12, 13]

Step 3: Sorted Array

After continuing this process, the array becomes fully sorted:

[5, 6, 7, 11, 12, 13]

---

Advantages of Heap Sort

1. Guaranteed O(n log n) Performance: Heap Sort guarantees O(n log n) performance in both the worst and best cases, unlike quick sort which can degrade to O(n²) in the worst case.
2. In-Place Sorting: Heap Sort doesn’t require additional memory (beyond the input array itself), making it space-efficient with O(1) extra space.
3. No Recursion Overhead: Unlike quick sort, Heap Sort doesn’t require deep recursive calls, making it more suitable for environments with limited stack space.

---

Limitations of Heap Sort

1. Not Stable: Heap Sort is not a stable sorting algorithm, meaning it doesn’t preserve the relative order of equal elements. This can be important when sorting objects with multiple attributes.
2. Less Cache-Friendly: Heap Sort’s access patterns are less cache-friendly compared to algorithms like quick sort, which tends to perform better in practice due to its locality of reference.
3. Generally Slower Than Quick sort: Although Heap Sort guarantees O(n log n) time complexity, quick sort is typically faster in practice due to lower constant factors and better cache performance.

---

Conclusion

Heap Sort is a reliable sorting algorithm with guaranteed O(n log n) performance, making it suitable for large datasets. Its in-place nature ensures low memory overhead, but it is not as fast in practice as algorithms like quick sort due to its less efficient memory access patterns. Despite its limitations, Heap Sort is a strong choice when stability is not a concern and predictable performance is essential.

For more details on how Heap Sort compares to other algorithms, refer to the How to Do Heap Sort in Python article.

For further reading on sorting algorithms in C++, go to the articles:

• Shell Sort in C++

Have fun and happy researching!