Priority queue is an Abstract Data Type where each item has a priority, and the highest or lowest priority item is removed first.
Unlike a normal queue, items are not removed only by insertion order.
Common operations:
- Insert an item with a priority
- Peek at the next item
- Remove the next item
Priority queues are commonly implemented with a heap.
Typical time complexity with a heap:
- Insert: O(log n)
- Peek: O(1)
- Remove next item: O(log n)
Priority queues are useful for scheduling, Dijkstra’s shortest path algorithm, event simulation, and task processing.
flowchart LR A["task A: priority 3"] --> Heap["priority queue"] B["task B: priority 1"] --> Heap C["task C: priority 2"] --> Heap Heap --> Next["next: task B"]
Anki
id: priority-queue-definition deck: Computer Science::Data Structures tags: data-structures priority-queue
Q: In a priority queue, which item comes out next? A: The item with the highest or lowest priority, depending on how the queue is configured.
id: priority-queue-vs-queue deck: Computer Science::Data Structures tags: data-structures priority-queue queue
Q: Why would an emergency room use priority queue behavior instead of normal queue behavior? A: Patients with more urgent needs should be handled before less urgent patients, even if they arrived later.