Heaps
Heaps or priority queues are a very powerful data structure that can be used to easily store information that has some intrinsic order
Last updated
Heaps or priority queues are a very powerful data structure that can be used to easily store information that has some intrinsic order
Last updated
Heaps can be implemented as trees under the hood, but some are also implemented using arrays. I have chosen to stick to the implementation I was taught and park heaps under Trees
Find min/max:
Insert:
Remove:
Heapify:
In Python, heapq
is defaults to using a min heap. This might not be what you want by default. The only way to make heapq
work as a max heap is by inverting the values inserted
K-smallest implies using a k-sized max heap, removing the maximum element if the size becomes > k
K-largest implies using a k-sized min heap instead
Simulate the median by having a max heap for the elements to the left of the median and a min heap for the elements to the right of the median
Sometimes, the information required from a k-sized heap can be replicated by using Quick Select. The benefit of doing so is that the runtime can be reduced to whereas with heaps, it would be