- stores elements & supports following operations:
- in $O(log(n))$
- add an element
- remove min/max element
- in $O(1)$
- find the min/max element
- creates priority queue
- heaps are implemented with a binary tree array
- smallest element in all subtrees is at the root
- parent.val <= child.val always maintained
- used when you need to repeatedly find the single max or min element
- a rarer type of problem is when you need to find a median
- this can be solved with two heaps, harder type of problem
- you can also push a tuple to a heap, i.e (3, "apple")
- the first value is used for the queue, second value is used for ties (lower letter value of a will win against b cause it is "smaller")
- can keep top $k$ contenders for max or min by using the opposite type of heap
- when doing repeated heap operations, sometimes you can optimize from $O(nlogn)$ to $O(n)$ by using [[Monotonic|Monotonic Stack]], depending on problem constraints
```
# In Python, we will use the heapq module
# Note: heapq only implements min heaps
from heapq import *
# Declaration: heapq does not give you a heap data structure.
# You just use a normal list, and heapq provides you with
# methods that can be used on this list to perform heap operations
heap = []
# Add to heap
heappush(heap, 1)
heappush(heap, 2)
heappush(heap, 3)
# Check minimum element
heap[0] # 1
# Pop minimum element
heappop(heap) # 1
# Get size
len(heap) # 2
# Bonus: convert a list to a heap in linear time
nums = [43, 2, 13, 634, 120]
heapify(nums)
# Now, you can use heappush and heappop on nums
# and nums[0] will always be the minimum element
```