Why Use Heaps?

Heaps are fast because they're designed to be hyper-efficient for one task: finding the minimum or maximum element in a collection. We don't need to be able to search in the heap, or even index into it. We just need to quickly find the minimum or maximum element and maintain that order as we add and remove elements.

Big O Analysis

• insert: O(log(n)). We need to do one operation per "level" of the tree, that is, once for each parent of the node being inserted.
• peek: O(1). We just need to look at the root node.

Tip

The first level of a heap will have 1 element, i.e. the root. The second level will have up to 2 elements; the third level up to 4; etc.