Min-heap priority queue

Challenge

Build a min-priority-queue over ints using a binary heap.

Task

Implement the following priority queue, backed by a single array used as a binary min-heap. pq_pop_min always removes and returns the smallest value currently stored.

typedef struct pq pq_t;
pq_t *pq_create(int capacity);
int   pq_push(pq_t *p, int v);            /* 0 ok, -1 full */
int   pq_pop_min(pq_t *p, int *out_min);  /* 0 ok, -1 empty */
int   pq_size(pq_t *p);
void  pq_destroy(pq_t *p);

Input

• capacity: maximum number of elements (capacity > 0).
• v: the value to insert.
• out_min: where pq_pop_min writes the removed minimum.

Output

• pq_push: 0 on success, -1 if full.
• pq_pop_min: 0 on success (writing the smallest value through out_min), -1 if empty.
• pq_size: the current number of elements.

Example

pq_create(10)
push 5, 1, 7, 3
pop_min  ->   1
pop_min  ->   3
pop_min  ->   5
pop_min  ->   7
pop_min  ->   -1   (empty)

Edge cases

• Pop from an empty queue returns -1.
• Push into a full queue returns -1.

Rules

• O(log n) per push and pop, backed by a single array. Use sift-up on insert and sift-down on extract.

Why this matters

Priority queues schedule everything from OS processes to network packets to game AI events. The binary heap is the simplest implementation that gives O(log n) insertion and extract-min.

Input format

capacity > 0; v to push; out_min receives the popped minimum.

Output format

push/pop_min return 0 on success or -1 (full/empty); pop_min writes through out_min; size returns the count.

Constraints

O(log n) per op. Backed by a single array.

Starter code

typedef struct pq pq_t;
pq_t *pq_create(int capacity);
int   pq_push(pq_t *p, int v);
int   pq_pop_min(pq_t *p, int *out_min);
int   pq_size(pq_t *p);
void  pq_destroy(pq_t *p);

Common mistakes

Mixing up parent/child index formulas; sifting up when you meant down (or vice versa); forgetting that pop_min replaces root with last element before sifting.

Edge cases to handle

Pop from empty returns -1. Push when full returns -1.

Complexity

O(log n) push and pop. O(1) size.

Up next

• Heap sort