CHAPTER 6
Priority Queues (Heaps)
6.1 Yes. When an element is inserted, we compare it to the current minimum and change the minimum if the new
element is smaller. deleteMin operations are expensive in this scheme.
6.2
6.3 The result of three deleteMins, starting with both of the heaps in Exercise 6.2, is as follows:
6.4 (a) 4N
(b) O(N
2
)
(c) O(N
4.1
)
(d) O(2
N
)
6.5
/**
* Insert item x, allowing duplicates.
*/
void insert( const Comparable & x )
{
if( currentSize == array.size( ) - 1 )
array.resize( array.size( ) * 2 );
// Percolate up
int hole = ++currentSize;
for( ; hole > 1 && x < array[ hole / 2 ]; hole /= 2 )
array[ hole ] = array[ hole / 2 ];
array[0] = array[ hole ] = x;
}
6.6 225. To see this, start with i%=%1 and position at the root. Follow the path toward the last node, doubling i
when taking a left child, and doubling i and adding one when taking a right child.
6.7 (a) We show that H(N), which is the sum of the heights of nodes in a complete binary tree of N nodes, is
N%b(N), where b(N) is the number of ones in the binary representation of N. Observe that for N%=%0 and
N%=%1, the claim is true. Assume that it is true for values of k up to and including N 1. Suppose the left and
right subtrees have L and R nodes, respectively. Since the root has height , we have
The second line follows from the inductive hypothesis, and the third follows because L%+%R%=%N 1. Now the
last node in the tree is in either the left subtree or the right subtree. If it is in the left subtree, then the right
subtree is a perfect tree, and . Further, the binary representation of N and L are identical,
with the exception that the leading 10 in N becomes 1 in L. (For instance, if N%=%37%=%100101, L%=%10101.) It
is clear that the second digit of N must be zero if the last node is in the left subtree. Thus in this case,
b(L)%=%b(N), and
H(N)%=%N b(N)
If the last node is in the right subtree, then . The binary representation of R is identical to
N, except that the leading 1 is not present. (For instance, if N%=%27%=%101011, L%=%01011.) Thus
b(R)%=%b(N)%%1, and again
H(N)%=%N b(N)
(b) Run a single-elimination tournament among eight elements. This requires seven comparisons and
generates ordering information indicated by the binomial tree shown here.
The eighth comparison is between b and c. If c is less than b, then b is made a child of c. Otherwise, both
c and d are made children of b.
(c) A recursive strategy is used. Assume that N%=%2
k
. A binomial tree is built for the N elements as in part (b).
The largest subtree of the root is then recursively converted into a binary heap of 2
k
1
elements. The last
element in the heap (which is the only one on an extra level) is then inserted into the binomial queue
consisting of the remaining binomial trees, thus forming another binomial tree of 2
k
1
elements. At that point,
the root has a subtree that is a heap of 2
k
1
1 elements and another subtree that is a binomial tree of 2
k
1
elements. Recursively convert that subtree into a heap; now the whole structure is a binary heap. The running
time for N%=%2
k
satisfies T(N)%=%2T(N/2)%+%log N. The base case is T(8)%=%8.
6.8 a) Since each element in a min heap has children whose elements are greater than the value in the
element itself, the maximum element has no children and is a leaf.
c) Since the maximum element can be any leaf (the position of a node is determined entirely by the
value of its parent and children), all leaves must be examined to find the maximum value in a min
heap.
6.9 Let D
1
, D
2
, . . . ,D
k
be random variables representing the depth of the smallest, second smallest, and k
th
smallest elements, respectively. We are interested in calculating E(D
k
). In what follows, we assume that the
heap size N is one less than a power of two (that is, the bottom level is completely filled) but sufficiently
large so that terms bounded by O(1/N) are negligible. Without loss of generality, we may assume that the k
th
smallest element is in the left subheap of the root. Let p
j, k
be the probability that this element is the j
th
smallest element in the subheap.
Lemma.
For k > 1, .
Proof.
An element that is at depth d in the left subheap is at depth d%+%1 in the entire subheap. Since
E(D
j
%+%1)%=%E(D
j
)%+%1, the theorem follows.
Since by assumption, the bottom level of the heap is full, each of second, third, . . . , k 1
th
smallest
elements are in the left subheap with probability of 0.5. (Technically, the probability should be half 1/(N
1) of being in the right subheap and half%+%1/(N 1) of being in the left, since we have already placed the k
th
smallest in the right. Recall that we have assumed that terms of size O(1/N) can be ignored.) Thus
Theorem.
E(D
k
) log k.
Proof.
The proof is by induction. The theorem clearly holds for k%=%1 and k%=%2. We then show that it holds for
arbitrary k > 2 on the assumption that it holds for all smaller k. Now, by the inductive hypothesis, for any
1 j k 1,
Since f(x)%=%log x is convex for x > 0,
Thus
Furthermore, since p
j, k
%=%p
k j, k
,
From the lemma,
