Iteration
Heap
Sometimes you want to find the minimum in an Array that changes slowly. Here's an example:
It normally takes O(n) time to find the minimum element, but notice that there's actually a lot of redundant computation here - many of the same numbers show up in each minimum. A "Heap" data structure lets you take the minimum faster, by remembering the previous numbers you saw.
A Heap is a Tree where all the elements get bigger as you step down:
Finding the minimum element in a heap takes O(1) time, since it's just the root node of the heap.
Adding and removing elements takes O(log n) time, because adding and removing simply bubbles an element up or down and heaps are always balanced.
Suprisingly, you can create a Heap in O(n) time - this is faster than adding 1 element to the Heap at a time, which would take O(n log n) time. This is why creating a heap has a special name, called "Heapify".
Read Time Complexity O(1) to find minimum.
Insert/Delete Time Complexity O(logn)
Create Time Complexity O(n)
Example
Here's how you use a Heap to speed up the above example:
Other things to know
Heaps are stored as Arrays, and not as Trees. This is possible to do efficiently because they're always balanced, and elements are always added left-to-right. This allows them to be stored in the order of a BFS traversal. The above Heap is stored as [1, 5, 4, 6, 5, 8, 11, 10, 7, 8].
Heaps let you remove the root element, but typically not other elements. If you think you'll need to remove elements other than the min one, one common trick is to store a Set to remember those elements, and if you see them at the root of the heap, just pop them. The heap size effectively becomes n + |lazy|.
Implementation details
Most interview questions ask you to simply use Heaps, which doesn't require knowing how they work under the hood. Here's how they work for the curious.
Here's how you would implement these functions. You don't need to know this to actually use them.
Add/Remove - A heap is always stored as an array, even though it's a tree. This is only possible to do efficiently if adding and removing an element only touches the very last element in the array (aka the bottom-right leaf of the heap), because adds/removes to an array are only efficent if they're to the last element, O(1). This informs how adds and removes must work:
heap.add(x) - To add a new number x to the heap, put it as the bottom-right leaf and bubble it up, swapping the current element with its parent as needed to get the heap to increase as you walk down it again. This simply requires walking up the tree in one pass, so it's O(log n).
heap.pop() - To remove the top/smallest element, put the bottom-right leaf in its place, and then bubble it down. This simply requires walking down the tree in one pass, so it's O(log n).
heap = heapify(arr):
Heapify converts a disordered array into a heap array in O(n), by swapping values around.
You start by treating the array like a tree, the same way you treat the heap as a tree. You then do one iteration for each layer of the tree from bottom to top. Each iteration makes it so that all the elements on its layer are valid heaps, by taking its value and bubbling it down in one pass. At the end, all the elements are in the right place and you have a perfectly balanced heap. It's not obvious this takes O(n) unless you do the math: n⋅(41+82+163+324+645+1286+2567+...)=O(n)
heap.pop(x) - Not a not a typical operation, just here for the curious. It involves re-implementing your own heap. It's actually possible to remove any element instantly by tracking the index of each number in the heap, making memory O(2*n). It's better than the lazy solution if you have a ton of removes that make your heap size n + |lazy| very large.