- 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 ```