Priority Queue in C – Binary Heap Implementation

A priority queue in C is a queue where the element served next is the one with the highest priority, not the one that arrived first. Operating system schedulers, Dijkstra’s algorithm, event simulators, and heap sort are all built on it. The textbook way to implement one efficiently is a binary max-heap: a complete binary tree stored flat in an array, where every parent outranks its children. That single invariant makes both insertion and removal O(log n) — dramatically better than the O(n) sorted-array insert most old tutorials teach. This page implements the full structure — insert with sift-up, extract_max with sift-down — in tested, warning-free C89, using a struct so each entry carries both data and priority.

How It Works — Step by Step

1. The array is the tree: the root lives at index 0, and for any node at index i, its children sit at 2i+1 and 2i+2, its parent at (i-1)/2. No pointers needed — the arithmetic is the structure.
2. Insert = append + sift up: place the new item in the first free slot, then repeatedly swap it with its parent while it outranks the parent. At most log₂(n) swaps.
3. Extract = take root + sift down: the root is always the maximum. Remove it, move the last item to the root, then repeatedly swap it with its larger child until both children rank below it.
4. The heap is only partially ordered: it never sorts the whole array — it maintains just enough order that the maximum is always on top. That’s why it’s fast.

Inserting priorities 2, 5, 1, 4 gives the heap array [5, 4, 1, 2] — and extracting repeatedly returns 5, 4, 2, 1: perfect priority order from a never-fully-sorted array.

C Program to Implement a Priority Queue (Binary Heap)

/* Priority queue in C using a binary max-heap
 * Compile: gcc -ansi -Wall -Wextra priority_queue.c -o priority_queue */
#include <stdio.h>

#define MAX 64

struct item {
    int id;          /* the data — here, a job number */
    int priority;    /* larger number = served first  */
};

static struct item heap[MAX];
static int size = 0;

static void swap_items(int a, int b)
{
    struct item t = heap[a];

    heap[a] = heap[b];
    heap[b] = t;
}

/* Add an item, then sift it up until its parent outranks it */
static int insert(int id, int priority)
{
    int i;

    if (size == MAX) {
        return 0;                          /* queue full */
    }
    i = size++;
    heap[i].id = id;
    heap[i].priority = priority;

    while (i > 0 && heap[(i - 1) / 2].priority < heap[i].priority) {
        swap_items(i, (i - 1) / 2);
        i = (i - 1) / 2;
    }
    return 1;
}

/* Remove the highest-priority item: take the root, move the last
 * item to the top, then sift it down to its correct level */
static int extract_max(struct item *out)
{
    int i = 0;

    if (size == 0) {
        return 0;                          /* queue empty */
    }
    *out = heap[0];
    heap[0] = heap[--size];

    for (;;) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < size && heap[left].priority > heap[largest].priority) {
            largest = left;
        }
        if (right < size && heap[right].priority > heap[largest].priority) {
            largest = right;
        }
        if (largest == i) {
            break;
        }
        swap_items(i, largest);
        i = largest;
    }
    return 1;
}

int main(void)
{
    struct item job;
    int n, i, id, priority;

    printf("How many jobs? ");
    if (scanf("%d", &n) != 1 || n < 1 || n > MAX) {
        fprintf(stderr, "Invalid count.\n");
        return 1;
    }
    printf("Enter each job as: id priority\n");
    for (i = 0; i < n; i++) {
        if (scanf("%d %d", &id, &priority) != 2) {
            fprintf(stderr, "Invalid job.\n");
            return 1;
        }
        insert(id, priority);
    }

    printf("\nProcessing order (highest priority first):\n");
    while (extract_max(&job)) {
        printf("  job %d  (priority %d)\n", job.id, job.priority);
    }
    return 0;
}

How to Compile and Run

gcc -ansi -Wall -Wextra priority_queue.c -o priority_queue
./priority_queue

Sample Input and Output

Test 1 — four print jobs arriving in arbitrary order:

How many jobs? 4
Enter each job as: id priority
101 2
102 5
103 1
104 4

Processing order (highest priority first):
  job 102  (priority 5)
  job 104  (priority 4)
  job 101  (priority 2)
  job 103  (priority 1)

Test 2 — three jobs:

How many jobs? 3
Enter each job as: id priority
1 10
2 30
3 20

Processing order (highest priority first):
  job 2  (priority 30)
  job 3  (priority 20)
  job 1  (priority 10)

Both outputs are real captured runs of the exact code above.

Code Explanation

• The parent/child arithmetic: (i-1)/2, 2i+1, 2i+2 work because the tree is complete — filled level by level, left to right — which is exactly what “append at index size” maintains.
• Sift-down compares both children: the parent must be swapped with the larger child; swapping with the smaller one would put a lesser value above a greater one and silently break the heap invariant.
• Why a struct: real queue entries carry data (a job id, a pointer, a packet) plus a priority. Heapifying bare priorities — what many tutorials do — leaves you unable to know which job you just dequeued.
• Full/empty guards return status codes: insert and extract_max return 0/1 instead of printing inside the data structure. The caller decides what a full queue means — that separation is what makes the code reusable.
• Equal priorities: a binary heap is not stable — jobs with the same priority may come out in either order. If FIFO order among equals matters, add an insertion counter as a tie-breaker.

Time and Space Complexity

For a queue with frequent inserts — the normal case — the heap wins decisively: n inserts cost O(n log n) versus the sorted array’s O(n²).

What This Program Teaches

• Array-encoded binary trees — index arithmetic instead of pointers
• The heap invariant — partial order is enough when you only ever need the max
• Sift-up and sift-down — the two motions behind heaps and heap sort
• Struct-based ADT design — status-code returns, no I/O inside the data structure

Related C Programs

• Heap Sort in C — the same sift-down, used to sort an entire array
• Simple Queue in C — the FIFO baseline this structure generalizes
• Multiple Priority Queues in C — one queue per priority level
• Stack Implementation in C — the LIFO sibling

Test yourself: our free C Programming Quiz app for Android has 150+ questions with explanations for every answer.

Recommended Book

The C Programming Language by Kernighan & Ritchie is the foundation for the struct and array techniques used here. We’ve solved all of the book’s exercises. Also on Amazon.com.