I've seen this specific bug more times than I can count when developers first try to implement their own heap. You've got your array indices correct, your push logic seems fine, but the moment you start popping elements, the "Min-Heap" starts returning values that are definitely not the minimum. Let's look at a typical broken siftDown implementation.

// BROKEN MIN-HEAP SIFTDOWN
void siftDown(int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int smallest = index;

    if (left < size && data[left] < data[smallest]) {
        smallest = left;
    }
    
    if (right < size && data[right] < data[smallest]) {
        smallest = right;
    }

    if (smallest != index) {
        std::swap(data[index], data[smallest]);
        siftDown(smallest);
    }
}

The 'Wrong Child' Swap Bug

At first glance, this looks correct. It checks the left child, then the right child, and swaps with the smallest. But here is the subtle disaster: if both children are smaller than the parent, but the right child is actually the absolute minimum of the three, this code might work—but if you slightly tweak the logic or the comparison operators, it's easy to end up swapping the parent with the left child first, even if the right child was the better candidate for the root. Wait, actually, the logic above is mostly correct for a Min-Heap, but the real-world mistake I'm talking about is when learners do this:

// THE ACTUAL COMMON MISTAKE
if (left < size && data[left] < data[index]) {
    std::swap(data[left], data[index]);
    siftDown(left);
    return; // Exits early!
}
if (right < size && data[right] < data[index]) {
    std::swap(data[right], data[index]);
    siftDown(right);
}

Do you see the problem? The second snippet swaps with the left child the moment it finds any value smaller than the parent. It ignores the right child entirely if the left child was also smaller. This violates the heap property because the right child might have been even smaller than the left child. To maintain a valid Min-Heap, the absolute smallest of the parent and its two children must end up at the parent position.

Navigating the Array-Based Tree

Since a heap is a complete binary tree, we don't use pointers. We use a std::vector. I find it's easiest to remember the index math like this: if your current node is at i, its children are at 2i + 1 and 2i + 2. To go backward to the parent, you use (i - 1) / 2. Integer division handles the floor automatically, which is exactly what we want.

The Sift-Up Process for Insertions

When you add an element, you can't just drop it at the top; that would break the heap order immediately. Instead, you append it to the end of the vector (the bottom-rightmost leaf of the tree) and "bubble" it up. I call this siftUp. You compare the new element with its parent; if it's smaller (for a Min-Heap), you swap them and repeat the process until the element finds its rightful place or hits the root.

void siftUp(int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (data[index] < data[parent]) {
            std::swap(data[index], data[parent]);
            index = parent;
        } else {
            break; 
        }
    }
}

Maintaining Order during Deletions

Deleting the root is where the real work happens. You can't just remove the top element, or you'll have a hole in your tree. The trick I've always used is: swap the root with the very last element in the vector, pop the last element off (which is now the old root), and then siftDown the new root to its correct position. This preserves the "complete tree" structure while restoring the heap property.

Toggling Between Min and Max Heaps

The only structural difference between a Min-Heap and a Max-Heap is the comparison operator. If you're writing this for a production system, don't write two separate classes. I recommend using a template with a comparator, similar to how std::priority_queue works. By passing in std::less<T> or std::greater<T>, you can switch the entire behavior of your heap without changing a single line of the sifting logic.

📋 Practical Task

Build a Priority-Based Task Scheduler

Instead of a simple heap of integers, create a Task struct that contains a std::string description and an int priority. Implement a Max-Heap that stores these Task objects.

Your implementation must include:

• A push(Task t) method that maintains the Max-Heap property based on the priority value.
• A pop() method that removes and returns the task with the highest priority.
• A peek() method to view the top task without removing it.

Test your scheduler by inserting tasks in a random order (e.g., "Fix typo" priority 1, "Server crash" priority 10, "Update docs" priority 3) and verifying that "Server crash" is the first task popped from the heap.