Why Every Operation Is O(log n) or Better

add and remove each cost $O (h)$ , where $h$ is the height of the heap, and a complete binary tree of $n$ nodes has height about $lo g n$ . That height is small only because the tree is complete. An ordinary binary tree of $n$ nodes can be as tall as $n - 1$ , the degenerate, one-child-per-node shape from the search tree chapter:

╭───╮
│ 1 │
╰─┬─╯
  └───┐
    ╭─┴─╮
    │ 2 │
    ╰─┬─╯
      └───┐
        ╭─┴─╮
        │ 3 │
        ╰─┬─╯
          └───┐
            ╭─┴─╮
            │ 4 │
            ╰─┬─╯
              └───┐
                ╭─┴─╮
                │ 5 │
                ╰─┬─╯
                  └───┐
                    ╭─┴─╮
                    │ 8 │
                    ╰───╯

On a tree that tall, the operations would be $O (n)$ . A heap never takes that shape. add and remove keep the tree complete every time they run, so the height stays about $lo g n$ whatever order the elements arrive in.

The heap beside the flat designs

Since $h$ is about $lo g n$ , add and remove are each $O (lo g n)$ , and peek is $O (1)$ . Here is the heap beside the flat designs from earlier in the chapter:

Operation	unsorted	sorted array	binary heap
`add`	$O (1)$ amortized	$O (n)$	$O (lo g n)$
`peek`	$O (n)$	$O (1)$	$O (1)$
`remove`	$O (n)$	$O (1)$	$O (lo g n)$

Suppose you run $n$ elements through the queue: $n$ adds and then $n$ removes. On a heap each of these costs $O (lo g n)$ , so the total is $O (n lo g n)$ . Every flat design costs $O (n^{2})$ for the same work.

A Balanced Search Tree as a Priority Queue

For the map, we moved past the linear designs to an AVL tree, a balanced binary search tree. An AVL tree can serve as a priority queue too. The smallest element is the leftmost node. peek follows left children from the root, and remove removes that node, so both are $O (lo g n)$ . add is the AVL tree’s own add, which is also $O (lo g n)$ . Keeping a reference to the smallest node would even make peek $O (1)$ .

So the costs are close to the heap’s. There are two reasons we use a heap anyway. First, a priority queue allows duplicates, and the search trees we built do not store them: add does nothing when the value is already in the tree. A search tree can be changed to hold duplicates, for example with a count in each node, but that is more work on top of the AVL tree. Second, a search tree keeps every element in sorted order, the same full order the sorted array keeps. A priority queue only needs the smallest element. The heap keeps just enough order for that.