Priority Queue (ADT)
A priority queue is an abstract data type in which each element has a 'priority' and the highest priority is served first.
QUEUE
Call
—
Size
0
peek()
empty
Backing array — a min-heap, index under each cell
Nothing queued
Queue order — next out first
Empty
Popped
Nothing popped yet
An empty queue, and 6 calls to make in order: push(5), push(3), push(8), push(1), pop(), pop().
Next
5 is the first value, so it goes to index 0 and it is the root. Nothing to compare it against and nowhere to climb.
Value (0–99)
Intuition
In a standard Queue, it's 'First Come, First Served'. In a Priority Queue, it's 'VIPs First'.
Imagine an Emergency Room. A patient with a heart attack (High Priority) is treated before someone with a cold (Low Priority), regardless of who arrived first.
Concept
A Priority Queue is an Abstract Data Type (ADT). It is defined by its behavior, not its implementation.
- Insert(item, priority): Add an item with an assigned priority.
- Peek(): View the highest priority item.
- Pop(): Remove and return the highest priority item.
How it Works
While you can implement a PQ using an unsorted array (O(1) insert, O(N) pop) or a sorted array (O(N) insert, O(1) pop), the most efficient standard implementation is a Binary Heap.
A Binary Heap allows both Insert and Pop in O(log N) time, offering the best balance.
Step-by-Step Breakdown
- Push: Type a number and press Push. A smaller number is a higher priority, as in the MinHeap below. The value goes to the end of the backing array and bubbles up past any larger parent.
- Pop: Press Pop to remove and return the front of the queue, the smallest value. The last element of the array moves into index 0 and sinks below any smaller child.
- Queue order: The queued values in the order pop() will return them, whatever order they arrived in. The first of them is what peek() reads: heap[0].
- Popped: Every value returned so far, beside what a first-in-first-out queue would have returned from the same pushes.
- Presets: Out of order, Interleaved and Drain each replay a fixed sequence of push and pop calls from an empty queue.
When to Use
- Dijkstra's Algorithm / A*: Fetching the next closest node.
- Huffman Coding: Building efficient compression trees.
- Scheduling: Operating system process scheduling by priority.
- Top K Elements: Keeping track of the largest K items in a stream.
When NOT to Use
- When simple FIFO behavior is required (use Queue).
- When you need to search for arbitrary elements (use a BST or Hash Map).
How to Identify
Keywords like 'k-th largest', 'k-th smallest', 'closest points', or 'task scheduler' are strong indicators for a Priority Queue (Heap).
Applying for software engineering roles? Free, no sign-up: