Complete Notes on Priority Queues
With Code Examples, Structures, Diagrams & Applications
Complete Notes on Priority Queues
With Code Examples, Structures, Diagrams & Applications
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 indexi:
- 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
- Implement Min Priority Queue using Min-Heap
- Merge K sorted arrays using Priority Queue
- Find K largest elements in stream
- Implement
increaseKey()in heap - 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
Last updated: Nov 12, 2025
Complete Notes on Priority Queues
With Code Examples, Structures, Diagrams & Applications
Complete Notes on Priority Queues
With Code Examples, Structures, Diagrams & Applications
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 indexi:
- 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
- Implement Min Priority Queue using Min-Heap
- Merge K sorted arrays using Priority Queue
- Find K largest elements in stream
- Implement
increaseKey()in heap - 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
Last updated: Nov 12, 2025