Implement Max Heap in C++ | Complete Guide with Code & Dry Runs

1. Introduction

When dealing with massive amounts of data, we often don't need to keep everything perfectly sorted. Sometimes, we only care about finding the "most important" element right away—like the highest priority task in a system or the largest number in a dataset. This is where a Heap comes in.

A Heap is a specialized, highly efficient array-based data structure that allows us to find and remove the maximum (or minimum) element incredibly fast. Instead of sorting the entire dataset, a heap maintains just enough mathematical order in the array to keep the top element at the very front.

Real-world applications include:

• Priority Queues: Handling VIP customers first or processing high-priority operating system interrupts.
• Scheduling algorithms: Managing timers and task executions.
• Top-K Problems: Quickly finding the top 10 highest-scoring players in a game without sorting the scores of a million players.

2. What is a Heap?

In simple terms, a Heap is just a standard array, but the elements are arranged according to a strict hierarchical rule based on their indices.

There are two main conditions an array must meet to be considered a Heap:

1. Contiguous Elements: The array is filled sequentially. There are no "gaps" in the data. If the heap has 5 elements, they occupy indices 0 through 4.
2. The Heap Property (The Hierarchy): Every element at a specific index i is mathematically linked to two other "derived" indices later in the array. In a Max Heap, the value at index i must always be greater than or equal to the values at its derived indices.

We often call index i the "parent index" and the two derived indices the "child indices" just to make it easier to talk about their relationship, even though they are all just sitting in a flat line in the array.

3. Types of Heap

There are two primary variations of the heap array:

Max Heap

• Definition: The value at any parent index is always greater than or equal to the values at its child indices.
• Property: Because of this rule, the absolute largest element in the entire array is always pushed to the very front (index 0).
• Example Array:[100, 80, 50, 40, 30, 10]
  • The element at index 0 (100) is larger than elements at index 1 (80) and index 2 (50).

Min Heap

• Definition: The value at any parent index is always less than or equal to the values at its child indices.
• Property: The absolute smallest element in the entire array is always at the very front (index 0).
• Example Array:[10, 30, 50, 80, 100, 60]

4. Problem Statement

The Goal: Implement a Max Heap data structure from scratch in C++.

You need to create a class that manages a collection of numbers in a standard array (or vector) and supports the following operations efficiently:

• insert(val): Adds a new value to the heap array while maintaining the strict index hierarchy.
• extractMax(): Removes and returns the largest value (at index 0) and reorganizes the array.
• getMax(): Returns the largest value without removing it.

5. Array Representation & The Math

How do we define this strict hierarchy using math? For any element at index i in our array, we can find its related indices using simple formulas:

• Left Child Index = 2 * i + 1
• Right Child Index = 2 * i + 2
• Parent Index = (i - 1) / 2 (using standard integer division, dropping any decimals)

Let's test this with an example Max Heap array:Array = [100, 80, 50, 40, 30, 10]

Let's look at the element 80, which is sitting at index 1:

• What is its Left Child?2 * 1 + 1 = 3. Index 3 holds 40. (Since 80 > 40, the Max Heap rule holds!)
• What is its Right Child?2 * 1 + 2 = 4. Index 4 holds 30. (Since 80 > 30, the rule holds!)
• What is its Parent?(1 - 1) / 2 = 0. Index 0 holds 100. (Since 100 > 80, the rule holds!)

This mathematical relationship is the beating heart of a heap.

6. Key Observations

Before jumping into code, note these crucial traits:

1. The Max is Free: Because the parent is always larger than its children, the absolute largest element cascades all the way to index 0. Finding it takes $O(1)$ time.
2. Efficient Updates: When you add or remove an element, you don't need to re-sort the whole array. You only need to compare the changed element against its specific mathematical parent or children.
3. Logarithmic Time: Because the indices double (2i+1,2i+2), jumping from child to parent (or parent to child) skips huge portions of the array. The number of jumps required to go from the end of the array to the front is proportional to $\log(N)$.

7. Intuition

How do we maintain the heap property when data changes?

Inserting Data: When we insert a new element, we must place it at the very end of the array to ensure we don't leave any gaps. However, this new element might be larger than its calculated parent, violating our Max Heap math rule. To fix this, we compare the element with its parent and swap them if necessary, repeating this process until the element reaches a valid spot. We call this Heapify Up.

Removing Data: We want to extract the maximum element (at index 0). If we just delete index 0, every other element would shift left, completely destroying our careful mathematical indices! To fix this, we overwrite index 0 with the very last element in our array, and then delete the last position. The array sizes down cleanly. However, the new element at index 0 is likely too small. We fix this by comparing it with its children and swapping it with the largest child, moving it down the array until the math rules are restored. We call this Heapify Down.

8. Insert Operation

Step-by-step intuition:

1. Add the new value to the end of the array (using push_back).
2. Call heapifyUp() on this new last index to restore order.

C++ snippet:

void insert(int val) {
    heap.push_back(val);         // Add to the end of the array
    heapifyUp(heap.size() - 1);  // Restore the heap mathematical property
}

• Time Complexity:$O(\log N)$ because the element jumps through indices by halving them.
• Space Complexity:$O(1)$ auxiliary space.

9. Heapify Up

Logic: Compare the current element at index i with its parent at index (i-1)/2. If the current element is greater than the parent, they are out of order. Swap them, and update your current index i to be the parent's index.

Stopping Condition: Stop when you reach index 0 OR when the parent is greater than or equal to the current element.

C++ snippet:

void heapifyUp(int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (heap[i] > heap[parent]) {
            swap(heap[i], heap[parent]);
            i = parent; // Update i to check the next mathematical step up
        } else {
            break; // The math rules are satisfied
        }
    }
}

10. Get Maximum

Since the heap guarantees the largest element is at index 0, getting the maximum is trivial.

C++ snippet:

int getMax() {
    if (heap.empty()) throw runtime_error("Heap is empty!");
    return heap[0];
}

complete implementation:

#include <vector>
#include <algorithm> // for std::swap

class maxHeap {
  private:
    // The flat array storing our heap
    std::vector<int> heap;

    // Helper to restore math rules when adding to the back
    void heapifyUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[i] > heap[parent]) {
                std::swap(heap[i], heap[parent]);
                i = parent; // Move up to the parent's index
            } else {
                break; // Math rule is satisfied
            }
        }
    }

    // Helper to restore math rules when removing from the front
    void heapifyDown(int i) {
        int n = heap.size();
        while (true) {
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            int largest = i;

            // Find the largest valid value among index i and its calculated children
            if (left < n && heap[left] > heap[largest]) largest = left;
            if (right < n && heap[right] > heap[largest]) largest = right;

            // If the current index is not the largest, swap and continue down
            if (largest != i) {
                std::swap(heap[i], heap[largest]);
                i = largest;
            } else {
                break; // Math rule is satisfied
            }
        }
    }

  public:
    void push(int x) {
        // Add to the end of the array, then fix the order moving forward
        heap.push_back(x);
        heapifyUp(heap.size() - 1);
    }

    void pop() {
        // If empty, do nothing
        if (heap.empty()) return; 
        
        // Overwrite the front with the back, delete the back, then fix the order moving backward
        heap[0] = heap.back();
        heap.pop_back();
        
        if (!heap.empty()) {
            heapifyDown(0);
        }
    }

    int peek() {
        // Return the front element or -1 if empty
        if (heap.empty()) return -1;
        return heap[0];
    }

    int size() {
        // Return the number of elements in the array
        return heap.size();
    }
};

Applications

Where will you see Max Heaps used?

• Priority Queues: To fetch the most urgent event based on a priority number.
• Heap Sort: By extracting the max repeatedly from index 0 and placing it at the end of the array, you can sort data in $O(N \log N)$ time completely in-place.
• Top-K Problems: Finding the $K$ largest items in a massive stream of data.