Heaps have special properties that make it perfect for solving problems involving finding the min or max of something:
- It will always give you either its largest or smallest element
- It takes O(log(n)) time to add an item to a heap
- It takes O(1) time to remove the top element in a heap
Examples of questions that we could use heaps to solve are: find the shortest distance between two nodes in a weighted graph, keep track of the n largest digits.
Creating a heap
In Python, the two popular ways to create a heap is via either a
heapq. The difference between them is
heapq is a library that performs functions on a heap (which is a list), while PriorityQueue is a pre-built class.
heapq for these two reasons:
heapqallows you to start the heap with existing items
heapqallows you to print out the entire heap
heapq also tends to be a little faster because it is not threadsafe. However, interviewers do not care if you pick a fast library or not, so just use your favorite.
Our heap can simply be represented with an empty list:
Or we can initialized the list with existing items, and then use
heapify() to rearrange the list into the heap:
heapify() does not sort the heap, it only ensures the first/top-most item is the smallest item.
heapify() also takes O(n) time to arrange all the items in the heap.
If the items in the heap are tuples,
heapify() use the first value in the tuple to arrange by:
Adding an item to the heapO(log(n))
Add an item to the heap via the
Removing an item from the heapO(log(n))
To remove an item from a heap, use
heappop() . This returns the item with the lowest value in the heap:
Getting an item from the heapO(1)
Since the heap is a list, you can look at index 0 of the list to peek at the smallest value in the heap:
Tips and tricks #1
If you want to create a max heap (a heap that will return the maximum value), use a negative priority.
Tips and tricks #2
If tuples are stored in the heap,
heapq will attempt to arrange the items based on the first values of the tuples, and then the second values if the first values are equivalent. This is especially helpful to keep in mind when when you need to store extra data for solutions, like finding the shortest path in a weighted graph.