Heap Height and Analysis

The questions in this section are about a priority queue implemented as a binary min-heap. The height of a tree is the number of edges on the longest path from the root to a leaf. The root is at level $0$ .

Solution

Levels $0$ through $h - 1$ are full and hold $2^{h} - 1$ nodes. Level $h$ holds between $1$ and $2^{h}$ nodes. So

2^{h} \leq n \leq 2^{h + 1} - 1.

Taking $lo g_{2}$ of $2^{h} \leq n$ gives $h \leq lo g_{2} n$ . Taking $lo g_{2}$ of $n < 2^{h + 1}$ gives $h > lo g_{2} n - 1$ . So $h$ is about $lo g n$ .

Solution

add fills the next open slot and remove drops the last node, so the tree is complete after every operation. A complete binary tree of $n$ nodes has height about $lo g n$ , whatever the values are.

Solution

peek is $O (1)$ : it reads the root. add is $O (lo g n)$ : finding the next open slot and swimming up each take at most one step per level, and the height is about $lo g n$ . remove is $O (lo g n)$ : finding the last node and sinking down each take at most one step per level.

Solution

On a binary heap, $2 n$ operations at $O (lo g n)$ each cost $O (n lo g n)$ . On an unsorted array, the $n$ removes each scan in $O (n)$ , so the total is $O (n^{2})$ . On a sorted array, the $n$ adds each shift in $O (n)$ , so the total is also $O (n^{2})$ .