Complete Notes on Priority Queues

With Code Examples, Structures, Diagrams & Applications

---

1. Definition

Priority Queue is a special type of queue where each element has a priority, and elements are removed in order of priority (not FIFO).

• Highest priority element is dequeued first.
• Priority can be based on value (e.g., smallest/largest) or custom key.

---

Analogy

Hospital Emergency Room:
Patient with critical condition (high priority) is treated first, even if others arrived earlier.

---

2. Types of Priority Queue

Type	Dequeue Order
Min Priority Queue	Smallest element first
Max Priority Queue	Largest element first

---

3. Operations

Operation	Description	Time Complexity (Heap)
insert(x, priority)	Insert element with priority	O(log n)
extractMax() / extractMin()	Remove and return highest priority	O(log n)
peek()	View highest priority element	O(1)
increaseKey() / decreaseKey()	Update priority	O(log n)
delete()	Remove arbitrary element	O(log n)

---

4. Implementation Methods

| Method | Insert | Extract | Space | | Method | O(log n) | O(log n) | O(n) | | Binary Heap (Recommended) | O(log n) | O(log n) | O(n) | | Binary Search Tree | O(log n) avg | O(log n) avg | O(n) | | Unordered Array | O(1) | O(n) | O(n) | | Ordered Array | O(n) | O(1) | O(n) |

Best Choice: Binary Heap → Optimal for both operations.

---

5. Binary Heap (Most Common Implementation)

Complete Binary Tree where:

• Max-Heap: Parent ≥ Children
• Min-Heap: Parent ≤ Children

---

Array Representation

Root at index 1 (or 0)
For node at index i:

• Left Child: 2*i
• Right Child: 2*i + 1
• Parent: i/2

---

Max-Heap Example (Array)

Index:   1   2   3   4   5   6   7
       [100, 80, 70, 60, 50, 40, 30]

Tree Structure

         100
       /     \
     80       70
    /  \     /  \
  60   50   40   30

---

6. Code: Max Priority Queue using Max-Heap (Array)

#include <stdio.h>
#define MAX 100

typedef struct {
    int heap[MAX];
    int size;
} PriorityQueue;

void init(PriorityQueue* pq) {
    pq->size = 0;
}

// Swap two elements
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Heapify up (after insert)
void heapifyUp(PriorityQueue* pq, int i) {
    while (i > 1 && pq->heap[i] > pq->heap[i/2]) {
        swap(&pq->heap[i], &pq->heap[i/2]);
        i = i / 2;
    }
}

// Insert element
void insert(PriorityQueue* pq, int value) {
    if (pq->size >= MAX - 1) {
        printf("Queue Full!\n");
        return;
    }
    pq->heap[++pq->size] = value;
    heapifyUp(pq, pq->size);
}

// Heapify down (after extract)
void heapifyDown(PriorityQueue* pq, int i) {
    int largest = i;
    int left = 2 * i;
    int right = 2 * i + 1;

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

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

// Extract maximum
int extractMax(PriorityQueue* pq) {
    if (pq->size == 0) {
        printf("Queue Empty!\n");
        return -1;
    }
    int max = pq->heap[1];
    pq->heap[1] = pq->heap[pq->size--];
    heapifyDown(pq, 1);
    return max;
}

// Peek max
int peek(PriorityQueue* pq) {
    return (pq->size > 0) ? pq->heap[1] : -1;
}

// Print heap
void printPQ(PriorityQueue* pq) {
    for (int i = 1; i <= pq->size; i++)
        printf("%d ", pq->heap[i]);
    printf("\n");
}

// Example Usage
int main() {
    PriorityQueue pq;
    init(&pq);

    insert(&pq, 10);
    insert(&pq, 30);
    insert(&pq, 20);
    insert(&pq, 50);
    insert(&pq, 40);

    printf("Priority Queue: ");
    printPQ(&pq);  // 50 40 20 10 30

    printf("Extract Max: %d\n", extractMax(&pq));  // 50
    printf("Extract Max: %d\n", extractMax(&pq));  // 40

    printf("After extraction: ");
    printPQ(&pq);  // 30 20 10

    return 0;
}

---

7. Min-Heap Priority Queue (Code Snippet)

// Change comparison in heapifyUp and heapifyDown
void heapifyUp(PriorityQueue* pq, int i) {
    while (i > 1 && pq->heap[i] < pq->heap[i/2]) {  // < for Min-Heap
        swap(&pq->heap[i], &pq->heap[i/2]);
        i = i / 2;
    }
}

---

8. Priority Queue with Custom Priority (Struct)

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

typedef struct {
    Element heap[MAX];
    int size;
} PQ;

void insert(PQ* pq, int data, int priority) {
    Element e = {data, priority};
    pq->heap[++pq->size] = e;
    // heapifyUp using e.priority
}

---

9. Applications of Priority Queue

Application	Use Case
Dijkstra’s Algorithm	Shortest path in graphs
Prim’s / Kruskal’s	Minimum Spanning Tree
Huffman Coding	Data compression
Task Scheduling	OS process scheduling
A Search*	Pathfinding in games/AI
Event Simulation	Discrete event simulation

---

10. Priority Queue using Linked List (Inefficient)

struct Node {
    int data, priority;
    struct Node* next;
};

void insert(struct Node** head, int data, int p) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->priority = p;

    if (*head == NULL || p > (*head)->priority) {
        newNode->next = *head;
        *head = newNode;
    } else {
        struct Node* temp = *head;
        while (temp->next != NULL && temp->next->priority >= p)
            temp = temp->next;
        newNode->next = temp->next;
        temp->next = newNode;
    }
}

Drawback: Insert → O(n), Extract → O(1)
Not suitable for large data.

---

11. Comparison: Heap vs Array vs List

Method	Insert	Extract	Best For
Heap	O(log n)	O(log n)	Balanced performance
Sorted Array	O(n)	O(1)	Frequent extraction
Unsorted Array	O(1)	O(n)	Frequent insertion
Linked List	O(n)	O(1)	Small data

---

12. Heap Sort using Priority Queue

void heapSort(int arr[], int n) {
    PriorityQueue pq;
    init(&pq);
    for(int i = 0; i < n; i++) insert(&pq, arr[i]);
    for(int i = n-1; i >= 0; i--) arr[i] = extractMax(&pq);
}

---

13. Diagram: Heap Operations

Insert 40

Before:
         50
       /    \
     40      20
    /  \
  10   30

After Insert 40 → Heapify Up:
         50
       /    \
     40      20
    /  \      \
  10   30      40  ← New

Extract Max (50)

Replace root with last (30), then heapify down:
         30
       /    \
     40      20
    /  \
  10   30
→ Swap with 40
         40
       /    \
     30      20
    /  \
  10   30

---

Summary Table

Feature	Priority Queue
Order	By priority (not insertion)
Best Implementation	Binary Heap
Insert	O(log n)
Extract	O(log n)
Peek	O(1)
Use	Scheduling, Graph algorithms

---

Practice Problems

1. Implement Min Priority Queue using Min-Heap
2. Merge K sorted arrays using Priority Queue
3. Find K largest elements in stream
4. Implement increaseKey() in heap
5. Simulate CPU scheduling (Priority Scheduling)

---

Key Takeaways

Priority Queue ≠ Regular Queue
Use Binary Heap for O(log n) operations
Essential for Graph Algorithms & Scheduling

---

End of Notes