Heap (Data Structure)

A heap is a binary tree storing keys at its nodes and satisfying the following properties:

• Order (heap)

  Heap-Order: for every internal node $v$ other than the root, $key(v)\ge key(parent(v))$.

  Link to original

• Complete Binary Tree: let $h$ be the height of the heap For $i=0,\dots ,h-1$, there are $2^i$ nodes of depth $i$. At depth $(h-1)$, the internal nodes are to the left of the external nodes.
• The last node of a heap is the rightmost node of maximum depth.

Height (heap)

Height of a Heap A heap storing $n$ keys has height $O(\log n)$. Proof by applying the complete binary tree property:

• Let $h$ be the height of a heap storing $n$ keys.
• Since there are $2^i$ keys at depth $i=0,\dots ,h-1$ and at least one key at depth $h$, we have $n\ge 1+2+4+\dots +2^{h-1}+1$.
• Hence, $n\ge 2^h$ or otherwise $h\le \log n$.

Link to original