Heap / Priority Queue
Maintains elements in a specific order, so the smallest or largest value can be accessed quickly.
The Approach
- Use a Min-Heap to keep track of the smallest elements or a Max-Heap for the largest.
- Insert elements into the heap (O(log n)).
- Extract the min/max element from the root of the heap (O(log n)).
- Often used to manage the 'top k' elements by maintaining a heap of size k.
Types of Heap / Priority Queue
Min-Heap
Keeps the smallest element at the root. Useful for finding the k-th smallest element.
A Min-Heap keeps the smallest element at the top.
Max-Heap
Keeps the largest element at the root. Useful for finding the k-th largest element.
A Min-Heap keeps the smallest element at the top.
Common Problems
Top K Frequent Elements
Heap / Priority Queue
Kth Largest Element in an Array
Heap / Priority Queue
Merge K Sorted Lists
Heap / Priority Queue
Find Median from Data Stream
Heap / Priority Queue
Task Scheduler
Heap / Priority Queue