Logarithms in Heaps (Insert and extract)

A binary heap is a complete binary tree, so with $n$ nodes it has height $O(\log n)$. Insert and extract operations bubble elements up or down the tree.

Inserting an element adds it to the bottom level and bubbles it up until the heap property holds. In the worst case, it bubbles all the way to the root, taking $O(\log n)$ swaps.

Similarly, extracting the max (or min) removes the root, replaces it with the last element, and bubbles down. This also takes $O(\log n)$ time. Heaps power priority queues with logarithmic operations.