Data Structure - Priority Queue
A Priority Queue is an extension of the queue. Unlike the "first in, first out" of a normal queue, every element in a priority queue is assigned a priority, and the dequeue operation always removes the element with the highest priority in the current queue.
Concept and Features of Priority Queue
You can compare it to the triage system in a hospital emergency room — the more critical a patient's condition, the sooner they are treated, even if they arrive later.
The core operations of a priority queue are different from those of a normal queue:
| Operation | Normal Queue | Priority Queue |
|---|---|---|
| Enqueue | Add element at the tail | Insert element with a priority |
| Dequeue | Return the element at the head (the earliest enqueued) | Return the element with the highest priority |
Comparison of Three Implementation Methods
Unordered Array
Ordered Linked List
Heap ★ Recommended
Heap implementation is optimal: it balances insertion and dequeue efficiency, and is the core dependency of algorithms such as Dijkstra's shortest path and Huffman coding.
The figure above compares the time complexity differences of the three implementation methods; heap implementation is the most balanced choice.
Implementation Based on Unordered Array
Example
#define MAX 100
/* Priority queue based on unordered array (max priority queue: the larger the value, the higher the priority) */
struct PriorityQueue {
int items[MAX];
int size; /* Current number of elements */
};
void initPQ(struct PriorityQueue* pq) { pq->size = 0; }
/* Enqueue: directly append to the end, O(1) */
void enqueue(struct PriorityQueue* pq, int value) {
if (pq->size >= MAX) return;
pq->items[pq->size++] = value;
}
/* Dequeue: traverse to find the maximum, O(n)
After finding it, move the last element to the removed position, and decrement size by 1 */
int dequeue(struct PriorityQueue* pq) {
if (pq->size == 0) return -1;
/* Find the index of the maximum value */
int maxIdx = 0;
for (int i = 1; i < pq->size; i++) {
if (pq->items[i] > pq->items[maxIdx]) {
maxIdx = i;
}
}
int maxVal = pq->items[maxIdx];
/* Move the last element to the deleted position (avoid a large number of moves) */
pq->items[maxIdx] = pq->items[--pq->size];
return maxVal;
}
int main() {
struct PriorityQueue pq;
initPQ(&pq);
enqueue(&pq, 5);
enqueue(&pq, 9);
enqueue(&pq, 3);
enqueue(&pq, 7);
printf("Dequeue (highest priority): %d\n", dequeue(&pq)); /* Output: 9 */
printf("Dequeue (highest priority): %d\n", dequeue(&pq)); /* Output: 7 */
printf("Dequeue (highest priority): %d\n", dequeue(&pq)); /* Output: 5 */
printf("Dequeue: %d\n", dequeue(&pq)); /* Output: 3 */
return 0;
}
Implementation Based on Ordered Linked List
Example
#include <stdlib.h>
struct Node {
int data;
int priority; /* Priority (the larger the value, the higher the priority) */
struct Node* next;
};
/* Enqueue: insert in descending order of priority, O(n) */
struct Node* enqueue(struct Node* head, int data, int priority) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->priority = priority;
newNode->next = NULL;
/* Empty list or the new node has the highest priority → insert at the head */
if (head == NULL || head->priority < priority) {
newNode->next = head;
return newNode;
}
/* Traverse to find the appropriate position (maintain descending order) */
struct Node* cur = head;
while (cur->next != NULL && cur->next->priority >= priority) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
return head;
}
/* Dequeue: remove the head node (highest priority), O(1) */
struct Node* dequeue(struct Node* head) {
if (head == NULL) return NULL;
struct Node* temp = head;
printf("Dequeue: data=%d, priority=%d\n", temp->data, temp->priority);
head = head->next;
free(temp);
return head;
}
int main() {
struct Node* pq = NULL;
pq = enqueue(pq, 10, 1); /* Data 10, priority 1 */
pq = enqueue(pq, 20, 5); /* Data 20, priority 5 */
pq = enqueue(pq, 30, 3); /* Data 30, priority 3 */
pq = dequeue(pq); /* Dequeue: data=20, priority=5 (highest priority) */
pq = dequeue(pq); /* Dequeue: data=30, priority=3 */
pq = dequeue(pq); /* Dequeue: data=10, priority=1 */
return 0;
}
HeapIt is currently the most common and balanced solution for implementing priority queues—both insertion and removal of the highest-priority element complete in O(log n) time. This content will be detailed in Chapter 15 on heaps.
Application Scenarios
| Scenario | Description |
|---|---|
| Task Scheduling | The operating system determines CPU execution order based on task priority. |
| Dijkstra's Shortest Path | Each time, select the unvisited node with the smallest distance, relying on a priority queue. |
| Huffman Coding | Repeatedly take out the two nodes with the lowest frequency and merge them to build an optimal coding tree. |