Overview
A heap stores values in a tree-shaped structure where each parent has priority at least as high as its children. Binary heaps usually store that tree in an array.
FoundationSource checked
Heap
Maintains a partial order so the minimum or maximum item can be found quickly.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Beginner
- Family
- Priority Queue
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 10
- Code example
- Ready
- Visualization
- Ready
Core Concepts
heap propertysift upsift downarray-backed tree
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 to implement priority queues.
- Use it when repeated minimum or maximum extraction is needed.
- Use it for heap sort, scheduling, and graph-search frontiers.
When Not to Use
- Avoid it when full sorted order or fast arbitrary search is needed.
- Avoid it when decrease-key or deletion by handle is required and the heap representation does not support it.
- Avoid it when stable ordering among equal priorities matters without tie-breakers.
What It Does
- Maintains a priority order
- Returns the top-priority item efficiently
Use Cases
- Priority queues
- Scheduling
- Heap Sort
Inputs
- Comparable priorities or values
Outputs
- Heap structure
- Top-priority item
Pseudocode
- 1.Store values in a nearly complete tree
- 2.Keep each parent ordered before its children
- 3.Insert by adding at the end and bubbling up
- 4.Remove the root by replacing it with the last value
- 5.Bubble down to restore the heap rule
Canonical Example
- Input
- operations = insert 5, insert 2, query 5
- Output
- query result = found
- Explanation
- Heap: The structure stores data so later operations can answer efficiently.
Implementation Notes
- Use sift-up after insertion and sift-down after root removal.
- For zero-based arrays, children are usually 2i + 1 and 2i + 2.
- Store explicit tie-breakers if equal-priority order matters.
Common Pitfalls
- Expecting the entire array representation to be sorted.
- Using incorrect parent or child index formulas.
- Forgetting to restore the heap property after insert or extract.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the same heap as a tree and as an array.
Step 1 of 5: Store values in a nearly complete tree
heap-tree-arrayNotes
A heap gives quick access to the next priority item, not a sorted sequence.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookAlgorithms textbook support for Heap's invariant, correctness argument, and asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Has variantsFibonacci Heap
Data Structures · Core
Fibonacci heaps are heap variants that support meldable priority queues with amortized decrease-key efficiency.
Compare with thisHas variantsLeftist Heap
Data Structures · Core
A leftist heap is a pointer-based priority queue with heap order.
Compare with thisHas variantsMin-Max Heap
Data Structures · Core
Min-max heaps are heap variants that maintain alternating min and max levels for double-ended priority queues.
Compare with thisHas variantsPairing Heap
Data Structures · Core
Pairing heaps are heap variants that represent meldable priority queues with self-adjusting tree linking.
Compare with thisRelationships
View full relationship pageUsed byHeap Sort
Heap Sort uses heap ordering to repeatedly extract extremal values.
GeneralizesPriority Queue
Priority queues are commonly implemented with heaps.
Related Algorithms
Tags
Data StructureTreePriority Queue