Heaps
This technique uses Min-Heap (or Max-Heap) whenever you need quick access to the smallest (or largest) item in input data.
A Min-Heap is a complete binary tree (that is, totally filled other than the rightmost elements on the last level) where each node is smaller than its children. The root, therefore, is the minimum element in the tree.
A Max-Heap is essentially equivalent. But each node is larger than its children. The root, therefore, is the maximum element in the tree.
How to Identify
- Data Structure Involves: Array, Heap, Queue
- Question Type: Find the smallest/largest/median/frequent ‘K’ elements of a set
Related Problems
| Problems | Difficulty | |
|---|---|---|
| 1 | K Closest Points to Origin | Medium |
| 2 | Top K Frequent Elements | Medium |
| 3 | Kth Smallest Element in a Sorted Matrix | Medium |
| 4 | Kth Largest Element in an Array | Medium |
| 5 | Merge K Sorted Lists | Hard |
| 6 | Find Median from Data Stream | Hard |