Binary Min-Heap Priority Queue

Challenge

A binary min-heap arranges items such that the root is always the minimum value. Heap insertion and extraction maintain the heap property in logarithmic time O(log N).

Your Task

Given the min-heap structure:

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} MinHeap;

Implement:

int heap_push(MinHeap *h, int val);
int heap_pop_min(MinHeap *h, int *out);

Rules

1. In heap_push:
   • If h == NULL or h->size >= h->capacity, return -1.
   • Insert val at index h->size, then sift up: compare with parent at (idx - 1) / 2. While idx > 0 and value is smaller than parent, swap with parent and update idx.
   • Increment h->size and return 0.
2. In heap_pop_min:
   • If h == NULL or out == NULL or h->size == 0, return -1.
   • Read minimum from root h->data[0] into *out.
   • Move last element h->data[h->size - 1] to h->data[0].
   • Decrement h->size.
   • Sift down: while child exists, find smaller child of 2 * idx + 1 and 2 * idx + 2. If root element is greater than smaller child, swap with smaller child and continue; otherwise break.
   • Return 0.

Example

int store[10]; MinHeap h = { store, 0, 10 };
heap_push(&h, 30); heap_push(&h, 10); heap_push(&h, 20);
int m;
heap_pop_min(&h, &m); // m == 10
heap_pop_min(&h, &m); // m == 20

Input format

h: pointer to MinHeap; val: int; out: pointer to int destination.

Output format

Returns 0 on success, -1 on empty/full or NULL.

Constraints

In-place array sift-up and sift-down. O(log N) operations.

Starter code

#include <stddef.h>

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} MinHeap;

int heap_push(MinHeap *h, int val) {
    (void)h; (void)val;
    return -1;
}
int heap_pop_min(MinHeap *h, int *out) {
    (void)h; (void)out;
    return -1;
}

Common mistakes

Off-by-one in child index computation; forgetting to check right child existence before comparing.

Edge cases to handle

Extracting from heap of size 1; pushing duplicate values; empty heap pop returns -1.

Background lessons

• Binary trees
• Arrays