aloalgo.comIntroduction to Heaps
A heap is a tree-based data structure that satisfies the heap property. It's commonly used to implement a priority queue, where you need quick access to the minimum or maximum element.What Problem Does a Heap Solve?
Imagine you need to repeatedly find and remove the smallest (or largest) element from a collection. Common scenarios:- Find the K largest elements in a stream
- Process tasks by priority
- Find the median of a data stream
- Merge K sorted lists efficiently
Heap Structure
A heap is a complete binary tree where each parent satisfies the heap property relative to its children. It's typically stored as an array for efficiency.The Heap Property
Min-heap: Every parent is smaller than or equal to its children. The root is the minimum.Max-heap: Every parent is larger than or equal to its children. The root is the maximum.Why Use a Heap?
| Operation | Array | Sorted Array | Heap |
|---|---|---|---|
| Get min/max | O(n) | O(1) | O(1) |
| Insert | O(1) | O(n) | O(log n) |
| Remove min/max | O(n) | O(1) | O(log n) |
Common Interview Problems
- Kth Largest Element: Maintain a min-heap of size K
- Merge K Sorted Lists: Use a heap to track the smallest element across lists
- Find Median from Data Stream: Use two heaps (min and max)
- Task Scheduler: Process highest priority tasks first
Was this helpful?
Company
Practice
Learn
© 2026 aloalgo.com. All rights reserved.