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.

Practice

1. What is the main characteristic of a priority queue compared to a regular queue?

easy

A. It does not allow insertion of new elements after creation

B. Elements are always dequeued in the order they were enqueued

C. It only stores elements of the same value

D. Elements are dequeued based on their priority, not just arrival order

Solution

1. Step 1: Understand queue behavior

   A regular queue removes elements in the order they arrive (FIFO).

2. Step 2: Understand priority queue behavior

   A priority queue removes elements based on priority, not arrival order.

3. Final Answer:

   Elements are dequeued based on their priority, not just arrival order -> Option D

4. Quick Check:

   Priority queue = priority-based removal [OK]

Hint: Priority queue removes highest priority first, not first-in [OK]

Common Mistakes:

• Thinking priority queue is same as FIFO queue
• Assuming elements must be unique
• Believing insertion order is always preserved

2. Which of the following is the correct way to declare a priority queue in C using the standard library?

easy

A. There is no built-in priority queue in standard C

B. struct priority_queue pq;

C. PriorityQueue pq = new PriorityQueue();

D. priority_queue<int> pq;

Solution

1. Step 1: Recall C standard library features

   The C standard library does not include a built-in priority queue type.

2. Step 2: Analyze options

   The other options show declaration syntax resembling C++ (priority_queue or struct) or Java (PriorityQueue class), none of which are standard in C.

3. Final Answer:

   There is no built-in priority queue in standard C -> Option A

4. Quick Check:

   C standard library lacks priority queue [OK]

Hint: C standard library lacks priority queue type [OK]

Common Mistakes:

• Confusing C with C++ STL syntax
• Assuming priority queue is built-in in C
• Using Java or C++ syntax in C code

3. Consider the following pseudocode for a max-priority queue operations:

insert(5)
insert(3)
insert(10)
extract_max()
insert(1)
extract_max()

What is the sequence of extracted elements?

medium

A. [10, 3]

B. [5, 3]

C. [10, 5]

D. [3, 1]

Solution

1. Step 1: Insert elements into max-priority queue

   Insert 5, 3, 10. The max element is 10.

2. Step 2: Extract max elements in order

   First extract_max() returns 10. Then insert 1. Next extract_max() returns 5 (next highest).

3. Final Answer:

   [10, 5] -> Option C

4. Quick Check:

   Extracted max elements = [10, 5] [OK]

Hint: Extract max returns highest inserted so far [OK]

Common Mistakes:

• Extracting elements in insertion order
• Confusing min and max priority
• Ignoring new insertions before extraction

4. The following C-like pseudocode tries to implement a priority queue insertion but has a bug:

void insert(int pq[], int *size, int value) {
  pq[*size] = value;
  (*size)++;
  int i = *size - 1;
  while (i > 0 && pq[i] < pq[(i - 1) / 2]) {
    int temp = pq[i];
    pq[i] = pq[(i - 1) / 2];
    pq[(i - 1) / 2] = temp;
    i = (i - 1) / 2;
  }
}

What is the bug in this insertion logic?

medium

A. It uses < instead of > for max-heap property

B. It increments size before inserting value

C. It swaps with wrong parent index

D. It does not update the heap after insertion

Solution

1. Step 1: Understand heap property for max-heap

   Max-heap requires parent >= children, so swap if child > parent.

2. Step 2: Analyze condition in while loop

   Condition uses pq[i] < pq[parent], which is correct for min-heap, not max-heap.

3. Final Answer:

   It uses < instead of > for max-heap property -> Option A

4. Quick Check:

   Max-heap needs child > parent to swap [OK]

Hint: Max-heap swaps when child > parent, not < [OK]

Common Mistakes:

• Using min-heap condition for max-heap
• Incorrect parent index calculation
• Not incrementing size correctly

5. You have a priority queue that stores tasks with integer priorities. You want to process tasks in order of highest priority but also keep track of the order tasks with the same priority were added. Which data structure modification best supports this?

hard

A. Use a simple array sorted by priority only

B. Use a max-heap with a timestamp to break ties

C. Use a queue ignoring priorities

D. Use a stack to process tasks in reverse order

Solution

1. Step 1: Understand requirement for priority and insertion order

   We want highest priority first, but for equal priority, process by insertion order.

2. Step 2: Choose data structure supporting priority and tie-break

   A max-heap with timestamps can break ties by earlier insertion time, preserving order among equals.

3. Final Answer:

   Use a max-heap with a timestamp to break ties -> Option B

4. Quick Check:

   Max-heap + timestamp = priority + insertion order [OK]

Hint: Add timestamp to priority for tie-breaking [OK]

Common Mistakes:

• Ignoring insertion order for equal priorities
• Using simple array without tie-break
• Using stack or queue ignoring priority