Overview & Concept
A Priority Queue is an abstract data structure where each element is associated with a priority value. Elements with higher priority are dequeued before elements with lower priority. It is most efficiently implemented via a Binary Heap (Max-Heap or Min-Heap), which maintains the heap property: every parent node has a higher (or equal) priority than its children. This yields guaranteed O(log n) insertions and extractions.
How It Works
Binary Heap Storage: Represented compactly inside a contiguous array where parent of index i is Math.floor((i - 1) / 2), and children are 2i + 1 and 2i + 2.
Sift-Up on Insertion: New elements are appended to the array end and bubbled up by repeatedly swapping with parent until heap invariant is restored.
Sift-Down on Extraction: The root element is extracted, the last array leaf is moved to the root, and trickled down by swapping with the maximum child.
Heapify Construction: An unordered array can be converted into a valid heap in linear O(n) time using bottom-up sift-down calls.
Step-by-Step Execution
Asymptotic Complexity Analysis
| Metric | Best Case | Average Case | Worst Case | Space Complexity |
|---|---|---|---|---|
| Complexity Bound | O(1) peek | O(log n) insert/extract | O(log n) tree depth | O(n) |
| Explanation | Optimal input arrangement minimizing operations. | Expected time for uniformly distributed randomized inputs. | Adversarial degenerate conditions requiring full traversal. | Auxiliary memory allocated beyond original input size. |
Pseudocode & Invariants
// Priority Queue (Binary Heap)
operation insert(value, priority):
heap.append({value, priority})
i = heap.length - 1
while i > 0 and heap[i] > heap[parent(i)]:
swap(heap[i], heap[parent(i)])
i = parent(i)
operation extract():
if heap.isEmpty(): return error
root = heap[0]
heap[0] = heap.pop()
siftDown(0)
return root- Shape Invariant: The underlying binary tree is always complete, filled on all levels except possibly the last from left to right.
- Heap Order Invariant: In a Max-Heap, for every node i other than root: A[parent(i)] ≥ A[i].
Advantages & Disadvantages
Key Advantages
- •Guaranteed O(log n) insertion and extraction of highest-priority items.
- •Memory efficient: zero pointer overhead, represented purely as a compact array.
- •Linear O(n) construction time via Floyd’s bottom-up build-heap algorithm.
Trade-offs & Limitations
- •Searching for arbitrary elements is slow (O(n) linear scan across array).
- •Deleting an arbitrary element requires O(n) search unless index mapping is maintained.
- •Unstable: identical priority elements may not preserve original arrival order.
Real-World Applications
Dijkstra's Shortest Path & Prim's MST
Greedy graph algorithms extracting the unvisited node with minimum tentative distance.
OS Process & Thread Scheduling
Operating system CPU schedulers selecting the runnable thread with highest dynamic priority.
Huffman Data Compression
Building optimal prefix trees by repeatedly extracting lowest-frequency symbol nodes.
Network Bandwidth & Packet Shaping
Quality of Service (QoS) network routers prioritizing latency-sensitive VoIP and video packets.
Decision Guide: When to Use
Ideal Scenarios
- ✓When you constantly need access to the maximum or minimum element.
- ✓When scheduling tasks with varying priorities or deadlines.
- ✓When implementing shortest path, MST, or A* pathfinding algorithms.
Consider Alternatives When
- ✕When frequent arbitrary search or key lookups are required.
- ✕When strict FIFO arrival ordering among identical keys must be preserved.
Explore Related Algorithms
Compare trade-offs and complexity across complementary tools in AlgoViz.