How to Implement Priority Queue in C: Simple Guide with Example

To implement a priority queue in C, use a struct to store elements with their priorities and maintain the queue as a sorted array or a heap. Insert elements by priority and remove the highest priority element first. This can be done using simple array operations or a binary heap for efficiency.

Syntax

A priority queue in C can be implemented using a struct to hold the element and its priority, and an array to store these structs. Key operations include insert (add element with priority) and extract (remove element with highest priority).

Example struct and function signatures:

• typedef struct { int data; int priority; } PQElement;
• void insert(PQElement queue[], int *size, PQElement element);
• PQElement extractMax(PQElement queue[], int *size);

c

typedef struct {
    int data;
    int priority;
} PQElement;

void insert(PQElement queue[], int *size, PQElement element);
PQElement extractMax(PQElement queue[], int *size);

Example

This example shows a simple priority queue using an array where elements are inserted in order of priority. The highest priority element is always at the front and extracted first.

c

#include <stdio.h>

#define MAX_SIZE 100

typedef struct {
    int data;
    int priority;
} PQElement;

void insert(PQElement queue[], int *size, PQElement element) {
    int i = *size - 1;
    // Move elements with lower priority to the right
    while (i >= 0 && queue[i].priority < element.priority) {
        queue[i + 1] = queue[i];
        i--;
    }
    queue[i + 1] = element;
    (*size)++;
}

PQElement extractMax(PQElement queue[], int *size) {
    PQElement max = queue[0];
    for (int i = 0; i < *size - 1; i++) {
        queue[i] = queue[i + 1];
    }
    (*size)--;
    return max;
}

int main() {
    PQElement queue[MAX_SIZE];
    int size = 0;

    insert(queue, &size, (PQElement){.data = 10, .priority = 2});
    insert(queue, &size, (PQElement){.data = 20, .priority = 5});
    insert(queue, &size, (PQElement){.data = 30, .priority = 1});

    printf("Extracted elements by priority:\n");
    while (size > 0) {
        PQElement e = extractMax(queue, &size);
        printf("Data: %d, Priority: %d\n", e.data, e.priority);
    }

    return 0;
}

Output

Extracted elements by priority:
Data: 20, Priority: 5
Data: 10, Priority: 2
Data: 30, Priority: 1

Common Pitfalls

Common mistakes when implementing a priority queue in C include:

• Not maintaining the order of elements by priority during insertion, which breaks the queue behavior.
• Forgetting to update the size of the queue after insertions or extractions.
• Using a fixed-size array without checking for overflow.
• Confusing priority order (higher number means higher priority or vice versa).

Always ensure the queue is sorted by priority after each insertion and size is correctly managed.

c

/* Wrong: Inserting without sorting */
void wrongInsert(PQElement queue[], int *size, PQElement element) {
    queue[*size] = element; // Just add at end
    (*size)++;
}

/* Right: Insert with sorting by priority */
void rightInsert(PQElement queue[], int *size, PQElement element) {
    int i = *size - 1;
    while (i >= 0 && queue[i].priority < element.priority) {
        queue[i + 1] = queue[i];
        i--;
    }
    queue[i + 1] = element;
    (*size)++;
}

Quick Reference

Priority Queue Operations Cheat Sheet:

Operation	Description	Typical Complexity
insert	Add element maintaining priority order	O(n) with array, O(log n) with heap
extractMax	Remove element with highest priority	O(n) with array, O(log n) with heap
peek	View element with highest priority without removing	O(1)
isEmpty	Check if queue is empty	O(1)

Key Takeaways

Use a struct with data and priority fields to represent queue elements.

Maintain the queue sorted by priority during insertion for correct behavior.

Always update the queue size after insertions and extractions.

Check for array overflow when using fixed-size arrays.

Consider using a binary heap for better performance on large data.