C++ Program For Heap Sort Using Recursion

Heap sort is an efficient, comparison-based sorting algorithm that leverages the properties of a binary heap data structure. In this article, you will learn how to implement heap sort using recursion in C++, along with its core concepts and practical application.

Problem Statement

Efficiently sorting an array of elements is a fundamental problem in computer science. Given an unsorted array of n elements, the challenge is to arrange them in ascending (or descending) order with optimal time and space complexity, especially for large datasets. Many algorithms exist, but some offer better performance guarantees than others in various scenarios.

Example

Consider an unsorted array of integers: [12, 11, 13, 5, 6, 7]

After applying heap sort, the array will be sorted in ascending order: [5, 6, 7, 11, 12, 13]

Background & Knowledge Prerequisites

To understand recursive heap sort, a basic understanding of the following concepts is essential:

• C++ Basics: Variables, loops, functions, and array manipulation.
• Arrays: How to declare, initialize, and access elements in a fixed-size array.
• Binary Trees: Basic structure of trees, parent-child relationships.
• Binary Heaps: Specifically, max-heaps (where the parent node is always greater than or equal to its children). Heap sort primarily uses a max-heap.
• Recursion: Understanding how a function calls itself to solve smaller subproblems.

Use Cases or Case Studies

Heap sort is a versatile sorting algorithm suitable for several applications due to its efficiency and stability.

• Priority Queues: The underlying heap data structure is ideal for implementing priority queues, where elements are extracted based on their priority.
• System Software: Used in operating systems for scheduling processes or managing memory due to its guaranteed O(n log n) time complexity.
• Real-time Systems: Its consistent performance (worst-case time complexity is the same as average-case) makes it suitable for applications where predictable timing is crucial.
• External Sorting: While not directly used for very large datasets that don't fit in memory, the principles of heap construction can be adapted for parts of external sorting algorithms.
• General Purpose Sorting: It's a solid choice when other stable sorts (like merge sort) are not strictly necessary, and quick sort's worst-case scenario needs to be avoided.

Solution Approaches

Heap sort primarily involves two phases: building a max-heap from the input array and then repeatedly extracting the maximum element from the heap. The heapify operation, which maintains the heap property, is where recursion is most naturally applied.

Recursive Heap Sort Implementation

This approach involves building a max-heap from the array and then repeatedly extracting the maximum element (which is always at the root) and placing it at the end of the array. The heapify function, responsible for maintaining the heap property, is implemented recursively.

// Heap Sort using Recursion
#include <iostream>
#include <vector> // Using vector for dynamic array behavior, can also use raw arrays

// Function to heapify a subtree rooted with node i
// n is size of heap
void heapify(std::vector<int>& arr, int n, int i) {
    // Step 1: Initialize largest as root
    int largest = i;
    int left = 2 * i + 1; // Left child
    int right = 2 * i + 2; // Right child

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

    // Step 3: If right child is larger than current largest
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    // Step 4: If largest is not root
    if (largest != i) {
        std::swap(arr[i], arr[largest]);

        // Step 5: Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

// Main function to perform heap sort
void heapSort(std::vector<int>& arr, int n) {
    // Step 1: Build max heap (rearrange array)
    // Start from the last non-leaf node and heapify downwards
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

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

        // Call heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

// Function to print an array
void printArray(const std::vector<int>& arr) {
    for (int x : arr) {
        std::cout << x << " ";
    }
    std::cout << std::endl;
}

int main() {
    // Step 1: Define an array to be sorted
    std::vector<int> arr = {12, 11, 13, 5, 6, 7};
    int n = arr.size();

    std::cout << "Original array: ";
    printArray(arr);

    // Step 2: Perform heap sort
    heapSort(arr, n);

    std::cout << "Sorted array: ";
    printArray(arr);

    // Step 3: Test with another array
    std::vector<int> arr2 = {4, 10, 3, 5, 1};
    n = arr2.size();

    std::cout << "Original array 2: ";
    printArray(arr2);

    heapSort(arr2, n);

    std::cout << "Sorted array 2: ";
    printArray(arr2);

    return 0;
}

Run

Sample Output

Original array: 12 11 13 5 6 7 
Sorted array: 5 6 7 11 12 13 
Original array 2: 4 10 3 5 1 
Sorted array 2: 1 3 4 5 10

Stepwise Explanation

1. heapify(std::vector& arr, int n, int i) Function:

• This function takes an array arr, its current size n (which shrinks during the sorting process), and an index i representing the root of the subtree to be heapified.
• It assumes the subtrees at left and right (children of i) are already heaps.
• It identifies the largest element among the root (i) and its children (2*i + 1, 2*i + 2).
• If the largest element is not the current root i, it swaps arr[i] with arr[largest].
• Crucially, after swapping, the subtree rooted at largest might no longer be a heap. Therefore, heapify is called recursively on the largest index to restore the heap property down the tree.

1. heapSort(std::vector& arr, int n) Function:

• Build Max Heap: The first phase is to convert the input array into a max-heap. This is done by iterating from the last non-leaf node (n/2 - 1) up to the root (0). For each of these nodes, heapify is called. This ensures that when the loop finishes, the entire array satisfies the max-heap property (largest element is at index 0).
• Extract Elements: After building the heap, the largest element is always at arr[0]. The second phase involves repeatedly extracting the maximum element:
• Swap the current root (arr[0]) with the last element of the heap (arr[i]).
• Decrement the heap size (i--), effectively removing the largest element from consideration for the heap.
• Call heapify on the new root (arr[0]) with the reduced heap size to restore the max-heap property. This recursive call ensures the next largest element floats to the top.
• This process continues until the heap size becomes 1. At this point, the array is sorted in ascending order.

Conclusion

Heap sort is an efficient, in-place sorting algorithm with a time complexity of O(n log n) in all cases (best, average, and worst). The recursive heapify function is fundamental to its operation, ensuring that the heap property is maintained as elements are rearranged and extracted. Its consistent performance makes it a reliable choice for various applications where guaranteed efficiency is required.

Summary

• Heap sort is a comparison-based sorting algorithm using a binary heap.
• It has an O(n log n) time complexity for best, average, and worst cases, making it very stable in performance.
• The algorithm involves two main phases: building a max-heap and repeatedly extracting the maximum element.
• The heapify function, implemented recursively, is crucial for maintaining the heap property by sifting down elements.
• Heap sort is an in-place algorithm, requiring minimal additional space (O(1) auxiliary space).
• It is used in priority queue implementations and system software due to its reliable performance.