Identify
- if you’re asked to find the top/smallest/frequent ‘K’ elements of a given set
- if you’re asked to sort an array to find an exact element
- if you require the top k elements use a Min Heap of size k, iterate through each element, pushing it into the heap (for python
heapq, invert the value before pushing to find the max), whenever the heap size exceeds k, remove the minimum element, that will guarantee that you have the k largest elements
Motive
- any problem that asks us to find the top/smallest/frequent ‘K’ elements among a given set falls under this pattern, the best data structure to keep track of ‘K’ elements is Heap
- this pattern will make use of the Heap to solve multiple problems dealing with ‘K’ elements at a time from a set of given elements
- there is no need for a sorting algorithm because the heap will keep track of the elements for you
Steps
- insert ‘K’ elements into the min-heap or max-heap based on the problem
- iterate through the remaining numbers and if you find one that is
larger than what you have in the heap, then remove that number
and insert the larger one.
Complexity
Time: O(n log k)
Space: O(k)
Common Problems