C++ Implementation of Heap Sort Algorithm¶

Heap sort is an efficient sorting algorithm based on the heap data structure. It leverages the properties of heaps (a complete binary tree structure) by repeatedly adjusting the heap to achieve sorting. Heap sort has a time complexity of O(n log n) and a space complexity of O(1), making it suitable for handling large-scale data.

1. Basic Concepts of Heap¶

A heap is a special type of complete binary tree, divided into max heaps and min heaps:
- Max Heap: Each parent node’s value is greater than or equal to its children’s values (parent ≥ child).
- Min Heap: Each parent node’s value is less than or equal to its children’s values (parent ≤ child).

Heap sort typically uses a max heap, as it allows extracting the maximum value from the root each time.

2. Storage Structure of Heap¶

A heap can be represented using an array, with the following index relationships:
- For a node at index i in the array:
- Parent node index: (i - 1) / 2 (floor division)
- Left child index: 2 * i + 1
- Right child index: 2 * i + 2

For example, the array [12, 11, 13, 5, 6, 7] corresponds to the heap structure:

        12
      /    \
    11      13
   /  \    /
  5    6  7

3. Core Steps of Heap Sort¶

Heap sort consists of two main steps: building the initial max heap and sorting process.

1. Build Initial Max Heap: Convert the unsorted array into a max heap. Start from the last non-leaf node and adjust upwards to ensure all subtrees satisfy the max heap property.
2. Sorting Process:
   - Swap the root (maximum value) with the last element of the unsorted portion.
   - Shorten the unsorted portion and adjust the heap (downward adjustment).
   - Repeat until all elements are sorted.

4. C++ Code Implementation¶

#include <iostream>
#include <vector>
using namespace std;

// Swap values of two integers
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// Adjust the subtree rooted at index i to be a max heap (iterative implementation)
void max_heapify(vector<int>& arr, int n, int i) {
    while (true) {
        int largest = i; // Assume current node is the largest
        int left = 2 * i + 1; // Left child index
        int right = 2 * i + 2; // Right child index

        // Compare with left child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        // Compare with right child
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest is not the current node, swap and continue adjusting
        if (largest != i) {
            swap(arr[i], arr[largest]);
            i = largest; // Adjust the swapped subtree
        } else {
            break; // Max heap property satisfied, stop adjustment
        }
    }
}

// Main heap sort function
void heap_sort(vector<int>& arr) {
    int n = arr.size();

    // Step 1: Build the initial max heap
    // Start from the last non-leaf node and move upwards
    for (int i = n / 2 - 1; i >= 0; --i) {
        max_heapify(arr, n, i);
    }

    // Step 2: Sorting process
    for (int i = n - 1; i > 0; --i) {
        // Swap the root (max value) with the last element of the unsorted portion
        swap(arr[0], arr[i]);
        // Adjust the remaining heap (size = i)
        max_heapify(arr, i, 0);
    }
}

int main() {
    // Test case
    vector<int> arr = {12, 11, 13, 5, 6, 7};
    cout << "Array before sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // Perform heap sort
    heap_sort(arr);

    // Output sorted result
    cout << "Array after sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

5. Code Explanation¶

1. swap Function: Simple swap of two integers.
2. max_heapify Function: Ensures the subtree rooted at i satisfies the max heap property by iteratively comparing the node with its children. If a child is larger, swap and continue adjusting the subtree.
3. heap_sort Function:
   - Heap Construction: Starting from the last non-leaf node (n/2 - 1), call max_heapify upwards to build the initial max heap.
   - Sorting: Swap the root (max value) with the end of the unsorted portion, reduce the unsorted portion size, and re-adjust the heap with max_heapify until all elements are sorted.

6. Output Result¶

Array before sorting: 12 11 13 5 6 7 
Array after sorting: 5 6 7 11 12 13 

Heap sort efficiently leverages heap properties to achieve a stable O(n log n) time complexity, making it a classic sorting algorithm. Beginners can master its core idea by understanding the heap construction and adjustment processes step by step.