Iteration

Lesson

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

You can add and remove elements in O(log n) time, because Heaps are always balanced. You can also create a Heap in O(n) time - this is actually faster than adding 1 element at a time to the Heap, 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(\log n)$

Create Time Complexity $O(n)$

Heaps are stored as Arrays, and not as Trees. The above Heap is stored as [1, 5, 4, 6, 5, 8, 11, 10, 7, 8], and you always store a Heap in the order of a BFS traversal.

Here's how you use a Heap to speed the above example up:

Mark as Completed: