Heap
Problems
| # | Problem | Difficulty | Hint | Tags |
|---|---|---|---|---|
| 374 | Top K Frequent Elements | Medium | HintWhat data structure can you use to store the counts of each number? Then, what data structure can you use to keep track of only the top k elements? |
#array #hashtable #divideandconquer #sorting #heap #bucketsort #counting #quickselect |
Heaps are binary trees that satisfy the property that its child nodes are greater than or equal to its own value.
Heaps are often used to implement priority queues where the smallest or largest element is at the front (root of the tree).
Python has a good heap library which is easy to implement. - heapq — Heap queue algorithm — Python 3.13.5 documentation
In python, you can just create a heap using a list like heap = [] and just put this list as an argument into the heapq functions.
The most common commands which you will implement.
heapq.heappush(heap, <item>) # used for pushing items to heap
heapq.heappop(heap) # used for popping elements from heap. This grabs the smallest element
Patterns
The most common pattern which indicates that you need to use a heap is when you see "at most k" or "at least k".
When you see those sentences, you create a heap and pop from the heap when the size is greater than k.
Use cases
Heaps are able to let you keep track of the current max or min in O(1) time.