Priority Queue Introduction and Concept in DSA C

Mental Model

A priority queue is a special list where each item has a rank, and the highest rank item is always taken out first.

Analogy: Imagine a line at a hospital emergency room where patients with more serious conditions get treated before others, no matter when they arrived.

Priority Queue:
[Item: 5, Priority: 1] -> [Item: 3, Priority: 3] -> [Item: 4, Priority: 2] -> null
Highest priority is 3 (item 3)

Dry Run Walkthrough

Input: Insert items with priorities: (5,1), (3,3), (4,2) into an empty priority queue

Goal: Insert items so that the highest priority item is always at the front

Step 1: Insert (5,1) into empty queue

[5:1] -> null

Why: First item becomes the start of the queue

Step 2: Insert (3,3) and place it before (5,1) because 3 > 1

[3:3] -> [5:1] -> null

Why: Higher priority items go to the front

Step 3: Insert (4,2) between (3,3) and (5,1) because 3 > 2 > 1

[3:3] -> [4:2] -> [5:1] -> null

Why: Keep queue sorted by priority descending

Result:

[3:3] -> [4:2] -> [5:1] -> null

Annotated Code

DSA C

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

// Node structure for priority queue
typedef struct Node {
    int data;
    int priority;
    struct Node* next;
} Node;

// Function to create a new node
Node* newNode(int d, int p) {
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = d;
    temp->priority = p;
    temp->next = NULL;
    return temp;
}

// Function to insert a new node in priority queue
void push(Node** head, int d, int p) {
    Node* start = *head;
    Node* temp = newNode(d, p);

    // Special case: The head is NULL or new node has higher priority than head
    if (*head == NULL || (*head)->priority < p) {
        temp->next = *head;
        *head = temp;
    } else {
        // Locate the node before the point of insertion
        while (start->next != NULL && start->next->priority >= p) {
            start = start->next;
        }
        temp->next = start->next;
        start->next = temp;
    }
}

// Function to print the priority queue
void printQueue(Node* head) {
    while (head != NULL) {
        printf("[%d:%d] -> ", head->data, head->priority);
        head = head->next;
    }
    printf("null\n");
}

int main() {
    Node* pq = NULL;
    push(&pq, 5, 1); // Insert item 5 with priority 1
    push(&pq, 3, 3); // Insert item 3 with priority 3
    push(&pq, 4, 2); // Insert item 4 with priority 2
    printQueue(pq);
    return 0;
}

if (*head == NULL || (*head)->priority < p) {

Check if new node should be new head due to higher priority or empty queue

while (start->next != NULL && start->next->priority >= p) {

Traverse to find correct insertion point maintaining descending priority order

*head = temp;

Insert new node at head when it has highest priority

start->next = temp;

Insert new node in middle or end maintaining priority order

Output

[3:3] -> [4:2] -> [5:1] -> null

Complexity Analysis

Time: O(n) because in worst case we traverse the entire queue to insert in correct position

Space: O(n) because each inserted item uses one node in memory

vs Alternative: Compared to a simple queue where insertion is O(1) but removal of highest priority is O(n), priority queue keeps highest priority at front for O(1) removal but insertion costs O(n)

Edge Cases

Empty queue

New node becomes the head immediately

DSA C

if (*head == NULL || (*head)->priority < p) {

New node has highest priority

New node inserted at the front

DSA C

if (*head == NULL || (*head)->priority < p) {

New node has lowest priority

New node inserted at the end after traversing all nodes

DSA C

while (start->next != NULL && start->next->priority >= p) {

When to Use This Pattern

When you need to always process the most important item first, use a priority queue to keep items sorted by importance automatically.

Common Mistakes

Mistake: Inserting new node without maintaining priority order
Fix: Traverse the queue to find the correct position where the new node's priority fits descending order

Summary

A priority queue stores items so that the highest priority item is always at the front.

Use it when you want to process items by importance rather than arrival order.

The key is to insert each new item in the right place to keep the queue sorted by priority.