Page 207 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

k+1
Notes There are exactly 2 – 1 nodes in the perfect left subtree. From the inductive hypothesis, there
k+1
are 2 – 1 nodes in the right subtree. Thus,
m = 1 + 2 – 1 + 2 – 1
k+1
k+1
k + 1
= 2 (k+1)+1 – 1.
h+1
Therefore, by induction M = 2 – 1 for all h ≥ 0, which proves the upper bound.
h
It follows from Theorem 10.1 that there exists exactly one complete binary tree that contains
exactly n internal nodes for every integer n ≥ 0. It also follows from
Theorem 10.1 that the height of a complete binary tree containing n internal nodes is h = [log
2
n].
Why are interested in complete trees? As it turns out, complete trees have some useful
characteristics. For example, in the preceding chapter you saw that the internal path length of a
tree, i.e., the sum of the depths of all the internal nodes, determines the average time for various
operations. A complete binary tree has the nice property that it has the smallest possible internal
path length:

Theorem 10.2

The internal path length of a binary tree with n nodes is at least as big as the internal path length
of a complete binary tree with n nodes.
extbfProof Consider a binary tree with n nodes that has the smallest possible internal path length.
Clearly, there can only be one node at depth zero--the root. Similarly, at most two nodes can be at
depth one; at most four nodes can be at depth two; and so on. Therefore, the internal path length
of a tree with n nodes is always at least as large as the sum of the fi rst n terms in the series

But this summation is precisely the internal path length of a complete binary tree!
Since the depth of the average node in a tree is obtained by dividing the internal path length of
the tree by n, Theorem 10.1 tells us that complete trees are the best possible in the sense that the
average depth of a node in a complete tree is the smallest possible. But how small is small? That
is, is does the average depth grow logarithmically with n. The following theorem addresses this
question:

Theorem 10.3

The internal path length of a complete binary tree with n nodes is
n
∑ ⎢ ⎣ log i ⎥ ⎦ = (n + 1) log (n + 1) – 2 ⎢ ⎣ log (n +1) ⎥ ⎦ +1 + 2.
⎥ ⎦
⎢ ⎣
2
2 2
i =1
extbfProof The proof of Theorem 10.3 is left as an exercise for the reader. From Theorem 10.3 you
may conclude that the internal path length of a complete tree is O(n log n). Consequently, the
depth of the average node in a complete tree is O(log n).
10.2.2 Implementation
A binary heap is a heap-ordered complete binary tree which is implemented using an array. In a
heap the smallest key is found at the root and since the root is always found in the fi rst position
of the array, finding the smallest key is a trivial operation in a binary heap.

In this section we will describe the implementation of a priority queue as a binary heap. As

shown in Figure 10.2, I define a concrete class called BinaryHeap for this purpose.

202 LOVELY PROFESSIONAL UNIVERSITY