Heap Sort, Build Heap in C++, and Priority Queue

This chapter dives into constructing binary heaps in $O(n)$ time complexity, mastering the Heap Sort algorithm, and leveraging the Priority Queue container in C++ Standard Template Library (STL) to solve real-world problems efficiently.

1. Why Do We Need This? (Problem Statement & Status Quo)

While standard comparison-based sorting algorithms like Merge Sort and Quick Sort achieve $O(n \log n)$ average time complexity, Quick Sort degrades to $O(n^2)$ in worst-case scenarios, and Merge Sort requires $O(n)$ auxiliary space overhead.

To overcome these constraints, we look to Heaps. A heap enables us to build a structured binary tree where the maximum (or minimum) element can be accessed in $O(1)$ time, sorted in $O(n \log n)$ time in-place ($O(1)$ extra space), and constructed from an unsorted array in linear $O(n)$ time. Furthermore, heaps underpin Priority Queues, which are vital for efficient task scheduling, operating system kernel processes, and packet routing in computer networks.

2. Core Mental Model / Analogy: The VIP Priority Queue

• Real-Life Analogy: Imagine standing in a standard queue at a bank where customers are normally served on a First-Come, First-Served (FCFS) basis. Suddenly, a high-profile VIP or wealthy account holder arrives. Instead of waiting at the back of the line, the manager pulls them straight to the front because their priority overrides the arrival order.
• Computer Science Mapping: A standard Queue operates on FIFO (First In, First Out). A Priority Queue, however, dequeues elements based on their assigned priority (highest or lowest value first), mirroring how an emergency video-call data packet leaps ahead of a background web-browsing packet in a network router.

3. Building a Max Heap in $O(n)$ Time: Step-Up vs. Step-Down

The Naive Approach: Step-Up

If we insert elements into a heap one by one by bubbling them upward ("step-up" or push), each insertion takes $O(\log n)$ time, resulting in a total time complexity of $O(n \log n)$.

The Optimal Approach: Step-Down (Heapify)

Instead of inserting elements one by one, we are given an entire unsorted array at once. We can convert it into a Max Heap in $O(n)$ time by starting from the last non-leaf node and working backward to the root, pushing nodes down into their correct positions.

Leaf Node Identification Formula

In a complete binary tree represented as an array of size $n$, the nodes from index $\lfloor n/2 \rfloor$ to $n-1$ are leaf nodes. They have no children, so they inherently satisfy heap properties.

• First Non-Leaf Node Index: $\left(\frac{n}{2}\right) - 1$

Child and Parent Index Mapping

Given a node at index $i$ (0-indexed array):

• Left Child Index: $2i + 1$
• Right Child Index: $2i + 2$
• Parent Index: $\lfloor \frac{i - 1}{2} \rfloor$

4. Step-by-Step Evolution of Build Max Heap (Code Implementation)

Below is the complete C++ implementation demonstrating how to build a Max Heap using the optimal Step-Down ($O(n)$) approach via an iterative or recursive heapify function.

#include <iostream>
#include <vector>

using namespace std;

// Heapify function to maintain Max Heap property (Step-Down approach)
void heapify(vector<int>& arr, int n, int i) {
    int largest = i;          // Initialize current node as largest
    int left = 2 * i + 1;     // Left child index
    int right = 2 * i + 2;    // Right child index

    // If left child is larger than parent
    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 the parent, swap and continue heapifying downward
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest); // Recursive call for the affected subtree
    }
}

// Function to build a Max Heap from an unsorted array in O(n) time
void buildMaxHeap(vector<int>& arr, int n) {
    // Start from the last non-leaf node and traverse backwards to root (index 0)
    int startIdx = (n / 2) - 1;

    for (int i = startIdx; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

// Utility function to print the array
void printHeap(const vector<int>& arr) {
    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;
}

int main() {
    vector<int> arr = {14, 15, 12, 22, 17, 20, 18, 24, 23, 30, 19};
    int n = arr.size();

    cout << "Original Array: ";
    printHeap(arr);

    buildMaxHeap(arr, n);

    cout << "Max Heap Array: ";
    printHeap(arr);

    return 0;
}

5. Heap Sort Algorithm: Mechanics & In-Place Strategy

Heap Sort takes a built Max Heap and sorts the array in ascending order in $O(n \log n)$ time using $O(1)$ auxiliary space.

Workflow Walkthrough

1. Build Max Heap: Transform the input array into a Max Heap in $O(n)$ time so the maximum element sits securely at the root (arr[0]).
2. Swap Root with Last Element: Exchange the maximum element at the root (arr[0]) with the last active element in the heap (arr[i]). The largest element is now in its final sorted position at the end of the array.
3. Shrink Heap Size: Reduce the active heap size boundary by 1 (i--), effectively locking the sorted element in place.
4. Restore Heap Property: Call heapify(arr, i, 0) on the root to bubble the new root element down to its correct position.
5. Repeat: Continue until the heap size is reduced to 1.

Complete Heap Sort Implementation (C++)

#include <iostream>
#include <vector>

using namespace std;

void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

// Heap Sort Algorithm (In-place, O(n log n))
void heapSort(vector<int>& arr, int n) {
    // Step 1: Build Max Heap
    for (int i = (n / 2) - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

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

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

int main() {
    vector<int> arr = {14, 15, 12, 22, 17, 20, 18, 24, 23, 30, 19};
    int n = arr.size();

    heapSort(arr, n);

    cout << "Sorted Array (Ascending): ";
    for (int val : arr) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

6. Real-World Practical Pitfalls & Edge Cases

• 0-Indexed vs. 1-Indexed Arrays: Mixing up index calculations (2*i + 1 vs 2*i) causes segmentation faults or corrupted tree structures. Always stay consistent with your indexing convention (0-indexed is standard in C++ STL).
• Ignoring Leaf Nodes: Running heapify on leaf nodes is redundant and wastes CPU cycles. Always begin loop execution from the first non-leaf node: $\lfloor n/2 \rfloor - 1$.
• Recursive Call Stack Overhead: Using recursive heapify consumes $O(\log n)$ call stack space. In production environments with extreme constraints, refactoring heapify into an iterative (while-loop) approach guarantees $O(1)$ auxiliary space complexity.
• Stability: Heap Sort is not a stable sorting algorithm because equal elements may have their relative order swapped during root exchanges and heap adjustments.

7. Priority Queue in C++ STL

The C++ Standard Template Library provides a built-in container adaptor called std::priority_queue housed within the <queue> header. By default, it operates as a Max Heap.

Comparison of Sorting and Queue Paradigms

Practical STL Code Demonstration

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    // 1. Max Priority Queue (Default: Largest element has highest priority)
    priority_queue<int> maxPQ;
    
    maxPQ.push(10);
    maxPQ.push(20);
    maxPQ.push(11);
    maxPQ.push(18);
    maxPQ.push(15);

    cout << "Max PQ Top Element: " << maxPQ.top() << endl; // Output: 20

    // Pop element
    maxPQ.pop();
    cout << "Max PQ Top After Pop: " << maxPQ.top() << endl; // Output: 18

    // Iterating and printing remaining elements
    cout << "Draining Max PQ: ";
    while (!maxPQ.empty()) {
        cout << maxPQ.top() << " ";
        maxPQ.pop();
    }
    cout << "\n\n";

    // 2. Min Priority Queue (Smallest element has highest priority)
    // Syntax: priority_queue<Type, Container, Comparator>
    priority_queue<int, vector<int>, greater<int>> minPQ;

    minPQ.push(10);
    minPQ.push(20);
    minPQ.push(11);
    minPQ.push(18);
    minPQ.push(15);

    cout << "Draining Min PQ (Ascending): ";
    while (!minPQ.empty()) {
        cout << minPQ.top() << " ";
        minPQ.pop();
    }
    cout << endl;

    return 0;
}

8. Summary and Key Takeaways

• Linear Heap Construction: Building a heap using the Step-Down (heapify) approach takes $O(n)$ time complexity, which is asymptotically superior to the naive $O(n \log n)$ insertion method.
• Non-Leaf Starting Point: Heap construction must always initiate from the first non-leaf node located at index $\left(\frac{n}{2}\right) - 1$.
• Heap Sort Performance: Heap Sort sorts elements in $O(n \log n)$ time and $O(1)$ space, making it optimal for memory-constrained production environments.
• In-Place Sorting Mechanism: By swapping the root maximum element with the last active boundary element and shrinking the heap size by 1, we eliminate the need for extra arrays.
• Priority Queue Utility: std::priority_queue abstracts heap logic, allowing developers to manage high-priority tasks, OS kernel processes, and network packet routers seamlessly.
• Max Heap vs. Min Heap STL Syntax: Default std::priority_queue<T> creates a Max Heap, whereas std::priority_queue<T, vector<T>, greater<T>> creates a Min Heap.
• Space Optimization Mindset: While recursive heapify implementations consume $O(\log n)$ stack space, converting them to iterative loops achieves strict $O(1)$ space complexity.