Min-Heap Priority Queues for Embedded Systems

1. The Priority Queue: Why We Need It in Embedded Systems

A priority queue is an abstract data type where each element has an associated "priority." Unlike a standard queue (FIFO), when you dequeue an element, you always get the one with the highest priority (or lowest, depending on the implementation).

In embedded systems, this is incredibly useful for managing tasks or events that are not equally important. For example:

• An RTOS scheduler uses a priority queue to decide which task to run next.
• A network stack might prioritize processing an acknowledgment packet over a data packet.
• A timer manager uses a priority queue to keep track of the next timer to expire.

Consider a common deferred interrupt handling pattern. An Interrupt Service Routine (ISR) should be as fast as possible. Instead of doing heavy processing inside the ISR, it can simply enqueue a task into a priority queue. A lower-priority main loop then dequeues and executes these tasks based on their importance.

While you could implement a priority queue with a sorted array or linked list, these approaches have performance trade-offs for insertion and extraction. A far more efficient solution is the binary heap.

2. The Binary Heap: An Efficient Implementation

A binary heap is a tree-based data structure that satisfies two key properties:

1. Shape Property: It is a complete binary tree. This means all levels are fully filled, except possibly the last level, which is filled from left to right.
2. Heap Property: For a min-heap, the value of each parent node is less than or equal to the values of its children. This ensures the smallest element is always at the root. (A max-heap is the opposite).

The "complete tree" property allows for a clever and highly memory-efficient implementation: storing the tree in a simple array, with no need for explicit pointer-based node structures.

The video below gives a great visual walkthrough of this array-based representation and the fundamental heap operations.

3. Implementing the Min-Heap in C

Let's translate these concepts into a practical C implementation. We'll start with the data structure and the core "heapify" functions that maintain the heap property.

3.1 Data Structures and Indexing

We can define our min-heap with a structure containing a pointer to the array, its current size, and its capacity. We'll also define helper macros for index calculations (using a 0-based array).

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// For a 0-indexed array



#define PARENT(i) ((i - 1) / 2)
#define LEFT_CHILD(i) (2 * i + 1)
#define RIGHT_CHILD(i) (2 * i + 2)

typedef struct {
    int *array;     // Pointer to the array of elements
    int count;      // Current number of elements in the heap
    int capacity;   // Maximum capacity of the heap
} MinHeap;

MinHeap* create_heap(int capacity) {
    MinHeap* h = (MinHeap*)malloc(sizeof(MinHeap));
    if (!h) return NULL;
    h->count = 0;
    h->capacity = capacity;
    h->array = (int*)malloc(capacity * sizeof(int));
    if (!h->array) {
        free(h);
        return NULL;
    }
    return h;
}

void destroy_heap(MinHeap* h) {
    if (!h) return;
    free(h->array);
    free(h);
}

// Helper function to swap two integers
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

3.2 Sift-Up and Sift-Down Operations

The magic of the heap lies in two functions: sift_up (also called heapify-up or bubble-up) and sift_down (heapify-down or bubble-down).

• sift_up: After inserting a new element at the end of the array, we call sift_up to move it upwards until the heap property is restored.
• sift_down: After replacing the root with the last element (during extraction), we call sift_down to move the new root downwards to its correct position.

This next video explains these two crucial operations in detail.

Here are the C implementations based on that logic:

// Sifts an element up to its correct position.
void sift_up(MinHeap *h, int index) {
    int parent_index = PARENT(index);
    // Keep swapping as long as we are not at the root and parent is larger
    while (index > 0 && h->array[parent_index] > h->array[index]) {
        swap(&h->array[parent_index], &h->array[index]);
        index = parent_index;
        parent_index = PARENT(index);
    }
}

// Sifts an element down to its correct position.
void sift_down(MinHeap *h, int index) {
    int left = LEFT_CHILD(index);
    int right = RIGHT_CHILD(index);
    int smallest = index;

    // Find the smallest among the node and its children
    if (left < h->count && h->array[left] < h->array[smallest]) {
        smallest = left;
    }
    if (right < h->count && h->array[right] < h->array[smallest]) {
        smallest = right;
    }

    // If the smallest is not the current node, swap and recurse
    if (smallest != index) {
        swap(&h->array[index], &h->array[smallest]);
        sift_down(h, smallest);
    }
}

3.3 Priority Queue Operations: Insert and Extract-Min

Now we can implement the main priority queue operations using our heapify functions.

• insert (enqueue): Add the element to the end of the array and call sift_up.
• extract_min (dequeue): Get the root, replace it with the last element, decrement the count, and call sift_down on the new root.

// Inserts a new element into the min-heap. Time Complexity: O(log n)
void insert(MinHeap *h, int value) {
    if (h->count == h->capacity) {
        printf("Heap is full. Cannot insert.\n");
        return;
    }
    // Insert new element at the end
    h->array[h->count] = value;
    // Sift it up to maintain heap property
    sift_up(h, h->count);
    h->count++;
}

// Extracts the minimum element from the heap. Time Complexity: O(log n)
int extract_min(MinHeap *h) {
    if (h->count == 0) {
        printf("Heap is empty.\n");
        return INT_MIN; // Or some error value
    }
    
    // The minimum element is always at the root
    int min_val = h->array[0];

    // Replace root with the last element
    h->array[0] = h->array[h->count - 1];
    h->count--;

    // Sift down the new root to maintain heap property
    if (h->count > 0) {
        sift_down(h, 0);
    }

    return min_val;
}

// Peek at the minimum element without removing it. Time Complexity: O(1)
int peek(MinHeap *h) {
    if (h->count == 0) {
        printf("Heap is empty.\n");
        return INT_MIN;
    }
    return h->array[0];
}

4. The Interview Differentiator: The decrease_key Operation

In many real-world scenarios, like Dijkstra's algorithm or updating event timers, you don't just insert and extract—you also need to decrease the priority (value) of an existing element.

A naive implementation would be to search the array for the element (O(n)), update its value, and then sift it up (O(log n)), for a total of O(n). We can do much better.

The key is to maintain an auxiliary data structure—often a hash map or a simple array—that tracks the current position of each element in the heap. This allows us to find any element in O(1) time. In an embedded system where task or timer IDs are often small integers, a simple array can serve as this map.

Let's modify our implementation. We'll add a positions array to our MinHeap struct. For simplicity, we'll assume the heap stores unique integer "items" (like task IDs), and the priority is a separate value. Let's adjust our structs.

typedef struct {
    int item_id;
    int priority;
} HeapNode;

typedef struct {
    HeapNode *nodes; // Array of nodes (item_id, priority)
    int *positions;  // Maps item_id -> array index
    int count;
    int capacity;
} MinHeap;

// In a real implementation, you would update create_heap, destroy_heap, 
// and swap to manage the 'positions' array as well.

// Decrease the priority of a given item. Time Complexity: O(log n)
void decrease_key(MinHeap *h, int item_id, int new_priority) {
    // Get the current index of the item using our map
    int index = h->positions[item_id];

    // Check if the new priority is actually lower
    if (h->nodes[index].priority < new_priority) {
        printf("New priority is not smaller than current priority.\n");
        return;
    }

    // Update the priority
    h->nodes[index].priority = new_priority;
    
    // The key was decreased, so we only need to sift up
    sift_up(h, index); // A modified sift_up that also updates the positions map
}

Note: A full implementation would require modifying sift_up and sift_down to update the positions array after every swap. This is a common follow-up question in an interview.

5. System-Level Trade-offs: Why Binary Heaps Win in Practice

For an interview at a top semiconductor company, it's not enough to just implement the algorithm. You need to discuss system-level implications. While more complex heaps like Fibonacci heaps offer better amortized time complexity for decrease_key (O(1)), they are rarely used in practice. Why?

The study "A Performance Study of Priority Queues" provides compelling, data-backed reasons that are perfect for an interview discussion.

Key discussion points for an interview:

• Memory Efficiency: The binary heap uses a single, contiguous array. This means one malloc call and predictable memory layout. Pointer-based structures like Fibonacci heaps require many small allocations for nodes, leading to higher memory fragmentation and overall consumption (as shown in Table 6.7 of the paper).
• Cache Performance: The array-based structure provides excellent spatial locality. When you access an element, nearby elements are often pulled into the cache. This drastically reduces memory latency. Pointer-heavy structures lead to scattered memory accesses, causing frequent cache misses, which negates their theoretical algorithmic advantages.
• Simplicity vs. Complexity: The binary heap is simple to implement and debug. The constant factors in its Big O notation are very small. The implementation complexity and high constant factors of Fibonacci heaps make them slower in all but the most decrease_key-intensive academic workloads.

Conclusion

You have now implemented a min-heap and understand how it serves as an efficient priority queue. More importantly, you can articulate the system-level reasons why this simple, array-based structure is often the best choice for real-world embedded systems.

Key Takeaways:

• A priority queue is an essential ADT for managing tasks and events in embedded systems.
• A binary heap provides an O(log n) implementation for insert and extract_min and O(1) for peek.
• Its array-based implementation is highly memory-efficient and cache-friendly, making it ideal for resource-constrained systems.
• The decrease_key operation, crucial for dynamic updates, can be optimized from O(n) to O(log n) by using an auxiliary map to track element positions.
• In practice, the binary heap's low overhead and superior cache performance often make it faster than theoretically superior but more complex heaps like the Fibonacci heap.

Preview of the Next Lesson:

We've covered a key data structure for prioritization. Next, we will tackle a fundamental structure for fast lookups: the hash table. We will learn how to implement a fixed-size hash table using linear probing, including handling deletions with tombstone markers, another classic topic for memory-constrained systems.