Offensive Security Researcher & Quantum Cryptography Analyst

Priority Queues Data Structure: Comprehensive Explanation and C Implementation

Abdul Wahab Junaid
Priority Queues: Comprehensive Explanation and C Implementation

I think of a priority queue as one of the most quietly essential data structures in computer science — it rarely gets the spotlight the way sorting algorithms do, but it sits underneath an enormous number of systems I interact with daily: task schedulers, pathfinding algorithms, event simulators, and even the Heap Sort algorithm I cover elsewhere in this series.

What makes priority queues interesting to me is the specific promise they make: instead of retrieving elements in the order I inserted them (like a normal queue) or in reverse order (like a stack), a priority queue always gives me back the element with the highest (or lowest) priority, regardless of insertion order. This article walks through how I build one from scratch using a binary heap.

History and Background

The concept of prioritized processing predates formal computer science, but the specific data structure I call a “priority queue,” implemented efficiently via a binary heap, traces back to J.W.J. Williams’ 1964 paper introducing Heapsort, where the binary heap itself was first formally described as an array-based structure.

The priority queue abstraction as a distinct concept — separate from the heap that implements it — became standard in algorithms literature through the 1970s, as computer scientists formalized abstract data types (ADTs) as a way of separating an interface (what operations are supported) from an implementation (how those operations are carried out). I find this separation valuable: a priority queue can be implemented with a binary heap, a Fibonacci heap, a pairing heap, or even a simple sorted list — each with different performance trade-offs — while still satisfying the same abstract contract.

Problem Statement

The problem I’m solving is this: I need a data structure that lets me repeatedly insert elements, each carrying some priority value, and efficiently retrieve (and remove) the element with the highest priority at any time — without having to re-sort the entire collection after every insertion or removal.

A naive approach — keeping a sorted array and always removing from the front — makes retrieval fast ($O(1)$) but insertion slow ($O(n)$, since I’d need to shift elements to maintain sorted order). A priority queue backed by a binary heap gives me a better balance: both insertion and extraction run in $O(\log n)$.

Core Concepts

How It Works

For my max-priority queue, here’s the sequence I follow for each supported operation:

Insertion:

  1. Add the new element at the end of the underlying array (the next available leaf position in the tree).
  2. Compare the new element to its parent; if it’s larger, swap them.
  3. Repeat step 2, moving upward, until the element is no longer larger than its parent, or it reaches the root.

Extract-max:

  1. Save the root element (the maximum) to return later.
  2. Move the last element in the array to the root position.
  3. Reduce the heap size by one (effectively removing the last, now-duplicated, slot).
  4. Compare the new root to its children; swap with the larger child if the root is smaller.
  5. Repeat step 4, moving downward, until the heap property is restored.
  6. Return the saved maximum value.

Peek-max: Simply return the root element without modifying the structure — this is $O(1)$ since the maximum is always at index 0 in a max-heap.

Working Principle

The internal logic of a priority queue backed by a binary heap relies on two things working together: the shape property (the tree is always complete, meaning every level is fully filled except possibly the last, which fills left to right) and the heap property (parents dominate children in priority).

The shape property is what lets me represent the tree compactly as an array with simple index arithmetic instead of needing explicit pointer-based tree nodes. The heap property is what guarantees the root always holds the maximum (or minimum) element. Every operation I perform — insertion or extraction — is really just a local repair operation: I make one small change (add a leaf, or replace the root) that might locally violate the heap property, and then I “bubble” that violation up or down the tree until the property is restored everywhere.

Mathematical Foundation

The height of a binary heap containing $n$ elements is crucial to the performance analysis, since it’s a complete binary tree. The height $h$ satisfies:

$$ h = \lfloor \log_2 n \rfloor $$

This follows because a complete binary tree of height $h$ has between $2^h$ and $2^{h+1} – 1$ nodes.

Since both heapifyUp and heapifyDown move an element along a single root-to-leaf path (or leaf-to-root path), the number of comparisons/swaps each performs is bounded by the height:

$$ T_{\text{insert}}(n) = O(\log n), \qquad T_{\text{extractMax}}(n) = O(\log n) $$

For peekMax, since the maximum always resides at index 0:

$$ T_{\text{peekMax}}(n) = O(1) $$

If I insert $n$ elements one at a time into an initially empty heap, the total cost is bounded by:

$$ \sum_{i=1}^{n} O(\log i) = O(n \log n) $$

This is the same asymptotic bound I’d get by building a heap element-by-element via insertion — worth contrasting with the tighter $O(n)$ bound achievable via the bottom-up buildMaxHeap procedure I describe in a separate article on building a heap, which processes all elements at once rather than inserting them individually.

Diagrams

Here is the overall operational flow of a priority queue:

flowchart TD
    A[Priority Queue] --> B[Insert element]
    B --> C[Place at end of array]
    C --> D[Heapify-Up: swap with parent while larger]
    D --> E[Heap property restored]

    A --> F[Extract-Max]
    F --> G[Save root value]
    G --> H[Move last element to root]
    H --> I[Heapify-Down: swap with larger child while smaller]
    I --> J[Return saved max, heap property restored]

And here is a diagram showing the array-to-tree mapping that makes this all possible:

flowchart LR
    A["Array index i"] --> B["Parent: (i-1)/2"]
    A --> C["Left child: 2i+1"]
    A --> D["Right child: 2i+2"]
    B --> E["Enables tree navigation without pointers"]
    C --> E
    D --> E

Pseudocode

INSERT(PQ, value)
    PQ.data[PQ.size] = value
    HEAPIFY-UP(PQ, PQ.size)
    PQ.size = PQ.size + 1

HEAPIFY-UP(PQ, i)
    while i > 0 and PQ.data[PARENT(i)] < PQ.data[i]
        swap PQ.data[PARENT(i)] and PQ.data[i]
        i = PARENT(i)

EXTRACT-MAX(PQ)
    if PQ.size == 0
        error "priority queue is empty"
    max = PQ.data[0]
    PQ.data[0] = PQ.data[PQ.size - 1]
    PQ.size = PQ.size - 1
    HEAPIFY-DOWN(PQ, 0)
    return max

HEAPIFY-DOWN(PQ, i)
    largest = i
    left = LEFT-CHILD(i)
    right = RIGHT-CHILD(i)

    if left < PQ.size and PQ.data[left] > PQ.data[largest]
        largest = left
    if right < PQ.size and PQ.data[right] > PQ.data[largest]
        largest = right

    if largest != i
        swap PQ.data[i] and PQ.data[largest]
        HEAPIFY-DOWN(PQ, largest)

PEEK-MAX(PQ)
    return PQ.data[0]

Step-by-Step Example

Let me walk through inserting the values 5, 15, 10, 20, 3 into an empty max-priority queue, one at a time.

Insert 5: Heap: $[5]$. Single element, nothing to sift up.

Insert 15: Heap: $[5, 15]$. Compare 15 (index 1) with parent 5 (index 0): $15 > 5$, swap. Heap becomes $[15, 5]$.

Insert 10: Heap: $[15, 5, 10]$. Compare 10 (index 2) with parent 15 (index 0): $10 < 15$, no swap needed. Heap stays $[15, 5, 10]$.

Insert 20: Heap: $[15, 5, 10, 20]$. Compare 20 (index 3) with parent 5 (index 1): $20 > 5$, swap → $[15, 20, 10, 5]$. Continue: compare 20 (now index 1) with parent 15 (index 0): $20 > 15$, swap → $[20, 15, 10, 5]$.

Insert 3: Heap: $[20, 15, 10, 5, 3]$. Compare 3 (index 4) with parent 15 (index 1): $3 < 15$, no swap needed.

Final heap array: $[20, 15, 10, 5, 3]$.

Extracting all elements (extract-max repeatedly):

This matches my tested C program exactly, which reported: Max element: 20 and extraction order 20 15 10 5 3.

Time Complexity

Space Complexity

A binary heap-based priority queue requires:

$$ O(n) $$

space to store $n$ elements, with no auxiliary structure needed beyond the array itself (unlike Merge Sort, which needs a separate output array). This is one of the properties I appreciate most about heap-based priority queues — they’re compact.

Correctness Analysis

I verify correctness by showing that both HEAPIFY-UP and HEAPIFY-DOWN preserve the heap property as a loop invariant.

Insertion correctness: Before insertion, I assume the heap property holds for all $n$ existing elements. Adding a new element at the next available leaf position may only violate the heap property along the single path from that leaf to the root (since every other parent-child relationship is untouched). HEAPIFY-UP walks exactly that path, swapping wherever the property is violated, and stops as soon as it finds a parent that is $\geq$ the current element (or reaches the root) — at which point the property holds everywhere.

Extraction correctness: Removing the root and replacing it with the last element may only violate the heap property along some path downward from the root (since all other subtrees remain valid heaps, by the inductive assumption that the heap was valid before extraction). HEAPIFY-DOWN walks down, always choosing to swap with the larger child (ensuring I don’t accidentally break the property in the subtree I move into), and stops once the current node is $\geq$ both its children or it reaches a leaf.

Since both operations only ever touch a single root-to-leaf path and always terminate in a heap-property-satisfying configuration, the structure remains a valid heap after every operation, by induction on the number of operations performed.

Advantages

Disadvantages

Applications

Implementation in C

Here is my tested max-priority queue implementation, backed by a binary heap stored in a dynamically allocated array:

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

typedef struct {
    int *data;
    int size;
    int capacity;
} PriorityQueue;

PriorityQueue* createPQ(int capacity) {
    PriorityQueue *pq = malloc(sizeof(PriorityQueue));
    pq->data = malloc(capacity * sizeof(int));
    pq->size = 0;
    pq->capacity = capacity;
    return pq;
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int parent(int i) { return (i - 1) / 2; }
int leftChild(int i) { return 2 * i + 1; }
int rightChild(int i) { return 2 * i + 2; }

// Restores the heap property by moving element at index i upward
void heapifyUp(PriorityQueue *pq, int i) {
    while (i > 0 && pq->data[parent(i)] < pq->data[i]) {
        swap(&pq->data[parent(i)], &pq->data[i]);
        i = parent(i);
    }
}

// Restores the heap property by moving element at index i downward
void heapifyDown(PriorityQueue *pq, int i) {
    int largest = i;
    int left = leftChild(i);
    int right = rightChild(i);

    if (left < pq->size && pq->data[left] > pq->data[largest])
        largest = left;
    if (right < pq->size && pq->data[right] > pq->data[largest])
        largest = right;

    if (largest != i) {
        swap(&pq->data[i], &pq->data[largest]);
        heapifyDown(pq, largest);
    }
}

void insert(PriorityQueue *pq, int value) {
    if (pq->size == pq->capacity) {
        printf("Priority queue is full\n");
        return;
    }
    pq->data[pq->size] = value;
    heapifyUp(pq, pq->size);
    pq->size++;
}

int extractMax(PriorityQueue *pq) {
    if (pq->size == 0) {
        printf("Priority queue is empty\n");
        return -1;
    }
    int max = pq->data[0];
    pq->data[0] = pq->data[pq->size - 1];
    pq->size--;
    heapifyDown(pq, 0);
    return max;
}

int peekMax(PriorityQueue *pq) {
    return pq->data[0];
}

int main() {
    PriorityQueue *pq = createPQ(10);

    insert(pq, 5);
    insert(pq, 15);
    insert(pq, 10);
    insert(pq, 20);
    insert(pq, 3);

    printf("Max element: %d\n", peekMax(pq));

    printf("Extracting in priority order: ");
    while (pq->size > 0) {
        printf("%d ", extractMax(pq));
    }
    printf("\n");

    free(pq->data);
    free(pq);
    return 0;
}

Sample Input and Output

Input: Insertions of 5, 15, 10, 20, 3 into an empty priority queue, followed by repeated extraction.

Output (verified by compiling and running the code above):

Max element: 20
Extracting in priority order: 20 15 10 5 3

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version