C++ Program To Implement Heap Sort

Heap Sort is an efficient, comparison-based sorting algorithm that organizes data by building a binary heap. In this article, you will learn how to implement Heap Sort in C++ step by step, understanding its core components and operations.

Problem Statement

Efficiently sorting a collection of data is a fundamental task in computer science. Whether dealing with numbers, strings, or custom objects, the ability to arrange them in a specific order (ascending or descending) is crucial for various applications, including search optimization, database management, and data analysis. Without an efficient sorting method, processing large datasets can become prohibitively slow and resource-intensive.

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 and implement Heap Sort effectively, readers should have a basic understanding of:

• C++ Fundamentals: Variables, data types, arrays, loops, and functions.
• Pointers: Basic understanding of how pointers work in C++ (though not heavily used in this specific implementation, it's generally helpful for array manipulations).
• Binary Trees: Basic concepts of tree data structures, nodes, parent-child relationships.
• Heaps: Specifically, the concept of a Max-Heap, where the value of each parent node is greater than or equal to the values of its children. This property is crucial for Heap Sort.

Use Cases or Case Studies

Heap Sort, while not always the fastest in practice due to cache performance, offers guarantees in its worst-case performance and is used in several practical scenarios:

• Priority Queues: Heaps are the underlying data structure for efficient priority queue implementations, where elements are extracted based on their priority.
• Operating System Scheduling: Used in some operating systems to schedule tasks based on their priority.
• Finding Kth Smallest/Largest Element: Heaps can efficiently find the k-th smallest or largest element in an array without fully sorting it.
• External Sorting: Can be adapted for sorting large datasets that do not fit into memory.
• Graph Algorithms: Sometimes used in algorithms like Dijkstra's or Prim's for maintaining a set of candidate edges or vertices.

Solution Approaches

Heap Sort works in two main phases: building a max-heap from the input array and then repeatedly extracting the maximum element from the heap.

Approach 1: Heap Sort Implementation

Heap Sort sorts an array by first transforming it into a max-heap and then repeatedly extracting the largest element (the root) and placing it at the end of the array.

// C++ Heap Sort Implementation
#include <iostream>
#include <vector>
#include <algorithm> // Required for std::swap

// Function to heapify a subtree rooted with node i
// n is the size of the heap
void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;       // Initialize 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 current largest
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

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

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

// Main function to perform Heap Sort
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // Step 1: Build a max-heap (rearrange array)
    // Start from the last non-leaf node and heapify upwards.
    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 max 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() {
    // Example 1
    std::vector<int> arr1 = {12, 11, 13, 5, 6, 7};
    std::cout << "Original array 1: ";
    printArray(arr1);
    
    heapSort(arr1);
    
    std::cout << "Sorted array 1: ";
    printArray(arr1);

    std::cout << "--------------------" << std::endl;

    // Example 2
    std::vector<int> arr2 = {4, 10, 3, 5, 1};
    std::cout << "Original array 2: ";
    printArray(arr2);
    
    heapSort(arr2);
    
    std::cout << "Sorted array 2: ";
    printArray(arr2);

    return 0;
}

Run

Sample Output

Original array 1: 12 11 13 5 6 7 
Sorted array 1: 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, and an index i (representing the root of a subtree).
• It ensures that the subtree rooted at i satisfies the max-heap property.
• It calculates the indices of the left (2*i + 1) and right (2*i + 2) children.
• It compares the root (arr[i]) with its children (arr[left], arr[right]) to find the largest among them.
• If the largest element is not the current root i, it swaps arr[i] with arr[largest] and then recursively calls heapify on the affected subtree to maintain the max-heap property downwards.

1. heapSort(std::vector& arr) Function:

• Build Max-Heap (First Phase):
• The first loop for (int i = n / 2 - 1; i >= 0; i--) iterates from the last non-leaf node up to the root (index 0).
• For each such node, it calls heapify to ensure that the subtree rooted at i becomes a max-heap. After this loop, the entire arr is transformed into a max-heap, with the largest element at index 0.
• Extract Elements (Second Phase):
• The second loop for (int i = n - 1; i > 0; i--) iterates from the last element of the array down to the second element (index 1).
• In each iteration:
• std::swap(arr[0], arr[i]): The largest element (at arr[0]) is swapped with the current last element of the unsorted part of the array (arr[i]). This places the largest element in its correct sorted position.
• heapify(arr, i, 0): The heap size is reduced by one (implicitly, by passing i as the new n), and heapify is called on the new root (index 0) to restore the max-heap property for the remaining unsorted portion. This ensures the next largest element will be at arr[0].

1. main() Function:

• Declares example std::vector arrays.
• Prints the original arrays.
• Calls heapSort() to sort the arrays.
• Prints the sorted arrays.

Conclusion

Heap Sort is a robust, comparison-based sorting algorithm that guarantees O(N log N) time complexity in all cases (best, average, and worst). It is an in-place sorting algorithm, meaning it requires minimal additional memory (O(1) auxiliary space). Its efficiency comes from its ability to efficiently find the next largest element using the heap data structure.

Summary

• Heap Sort is an efficient, comparison-based sorting algorithm with O(N log N) time complexity.
• It operates in two main phases: building a max-heap and then extracting elements.
• The heapify function is a core component, maintaining the max-heap property for a given subtree.
• The first phase builds a max-heap from the input array.
• The second phase repeatedly swaps the root (largest element) with the last element and then calls heapify on the reduced heap.
• Heap Sort is an in-place algorithm, requiring O(1) auxiliary space.