How do I actually map a tree structure into a flat array?

This is usually the part where people get stuck. You're thinking about nodes and pointers, but for a binary heap, we don't do that. Pointers are expensive and fragmented. Instead, we use a simple array where the "tree" is implicit. I always find it easiest to remember the math like this: if your current element is at index i, its left child is at 2i + 1 and its right child is at 2i + 2.

Going back up the tree is even simpler. The parent of any element at index i is always at (i - 1) / 2. Because C handles integer division by truncating, this works perfectly for both the left and right children. It's a bit of a "magic" formula, but it's what makes heaps so efficient—no malloc calls for every single node you insert.

What's the logic behind "bubbling up" and "sifting down"?

A heap is only a heap if it maintains its property: in a Max-Heap, the parent must always be greater than or equal to its children. When you insert a new element, you just toss it at the very end of the array. But that probably breaks the rules. To fix it, you "bubble up" (or sift-up). You compare the new element with its parent; if it's larger, you swap them. You keep doing this until the element finds a parent that's bigger than it, or it hits the root.

Extracting the root is the opposite. You take the root out, move the very last element in the array up to the root position, and then "sift down." You compare the new root with its children and swap it with the largest of the two. If you swap with the smaller child, you'll just break the heap property again immediately. Here is how that sift-down looks in practice for a Max-Heap:

void siftDown(Heap* h, int idx) {
    int largest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < h->size && h->data[left] > h->data[largest])
        largest = left;

    if (right < h->size && h->data[right] > h->data[largest])
        largest = right;

    if (largest != idx) {
        int temp = h->data[idx];
        h->data[idx] = h->data[largest];
        h->data[largest] = temp;
        siftDown(h, largest); // Keep going until it settles
    }
}

Do I need to write two entirely different versions for Min-Heaps and Max-Heaps?

Definitely not. I've seen students write two massive files for this, which is a maintenance nightmare. The only difference between a Min-Heap and a Max-Heap is the comparison operator. In a Max-Heap, you care about parent > child; in a Min-Heap, it's parent < child.

If you want to be fancy, you can pass a comparison function pointer into your heap operations. But if you're just building a specific one, just change the > to < in your sift functions. For example, if we were implementing a Min-Heap for something like Dijkstra's algorithm, that h->data[left] > h->data[largest] line in the code above would simply become h->data[left] < h->data[smallest]. The structural logic—the indices and the swapping—remains exactly the same.

📋 Practical Task

Build a System Process Priority Queue

Imagine you are writing a simplified OS scheduler. You need to implement a Max-Heap that stores "Process" structures. Each process has an int process_id and an int priority.

• Define a Process struct.
• Implement a PriorityQueue struct that contains an array of Processes and a current size.
• Write an insert_process function that adds a process and sifts it up based on the priority value.
• Write a pop_highest_priority function that removes the process with the highest priority and restores the heap property.

Test your implementation by inserting five processes with random priorities and popping them one by one to ensure they emerge in strictly descending order of priority.