Overview
A Priority Queue associates each item with a priority and supports efficient access to the next item by priority. It is commonly implemented with a heap.
FoundationSource checked
Priority Queue
Stores items so the highest- or lowest-priority item can be removed efficiently.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Beginner
- Family
- Abstract Data Type
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 1
- Relationships
- 8
- Code example
- Ready
- Visualization
- Ready
Core Concepts
priority keyextract minimumheap propertytie breaker
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(1)
Average
O(log n)
Worst
O(log n)
Space
O(n)
When to Use
- Use it when work should be processed by priority rather than arrival order.
- Use it when repeated extract-min or extract-max operations dominate.
- Use it for graph search, scheduling, and simulation event queues.
When Not to Use
- Avoid it when arbitrary lookup or ordered traversal is more important than priority extraction.
- Avoid it when priorities change often and the implementation lacks update support.
- Avoid it when FIFO or LIFO ordering is the actual requirement.
What It Does
- Stores items with priority keys
- Returns the minimum or maximum priority item efficiently
Use Cases
- Dijkstra-style graph search
- Scheduling and event simulation
- Best-first search
Inputs
- Items
- Keys or indexes
- Operations to support
Outputs
- Stored structure
- Query results
- Updated state
Key Formulas (1)
Heap parent index
parent(i) = ⌊(i − 1) / 2⌋
parent(i) = floor((i - 1) / 2)Finds the parent position in an array-backed binary heap.
Pseudocode
- 1.Prepare the inputs and state needed for Priority Queue.
- 2.Apply the priority key step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return stored structure.
Canonical Example
- Input
- insert A with priority 3, B with priority 1, C with priority 2
- Output
- pop returns B
- Explanation
- In a min-priority queue, B has the smallest priority key.
Implementation Notes
- Use a binary heap for a simple general-purpose priority queue.
- Store a tie-breaker counter when deterministic order among equal priorities matters.
- If decrease-key is unavailable, insert a new entry and skip stale entries when popped.
Common Pitfalls
- Forgetting that many implementations do not support efficient decrease-key.
- Using inconsistent tie-breaking for equal priorities.
- Assuming the internal heap array is fully sorted.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the structure layout and how operations move through or update it.
Step 1 of 4: Prepare the inputs and state needed for Priority Queue.
data-structures-mechanismNotes
Priority queues define an abstract operation; heaps are one common implementation.
Sources (1)
What each reference supports for this entry.
CLRS
BookTextbook reference for the algorithmic family and analysis of Priority Queue.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Used byDijkstra's Algorithm
Pathfinding · Foundation
Dijkstra implementations use a priority queue for tentative distances.
Compare with thisUsed byA* Search
Pathfinding · Core
A* commonly uses a priority queue ordered by f-score.
Compare with thisUsed byMoore-Hodgson Algorithm
Scheduling · Core
A max-priority queue removes the longest job from an overloaded prefix.
Compare with thisRelationships
View full relationship pageUsed byA* Search
A* commonly uses a priority queue ordered by f-score.
Used byDijkstra's Algorithm
Dijkstra implementations use a priority queue for tentative distances.
Used byPrim's Algorithm
Prim's Algorithm commonly stores candidate edges in a priority queue.
Related Algorithms
Tags
Data StructurePriority QueueHeapClassic