Min-heap priority queue

Challenge

Implement a min-priority-queue over ints:

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);

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.

Output format

See API.

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