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
6.5 public void insert( AnyType x )
{
if ( currentSize = = array.length – 1 )
enlargeArray( array.length * 2 + 1 );
}
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
subtree is a perfect tree, and
( ) log 1b R N=−
. 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,
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 = 2k. 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 2k − 1 elements. The last
6.9 Let D1, D2, . . . ,Dk be random variables representing the depth of the smallest, second smallest, and kth
smallest elements, respectively. We are interested in calculating E(Dk). 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 kth
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 kth
smallest in the right. Recall that we have assumed that terms of size O(1/N) can be ignored.) Thus
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,
( ) ( ) log log
j k j
E D E D j k j
−
+ + −
6.10 (a) Perform a preorder traversal of the heap.
(b) Works for leftist and skew heaps. The running time is O(Kd) for d-heaps.
6.13 (a) If the heap is organized as a (min) heap, then starting at the hole at the root, find a path down to a leaf by
taking the minimum child. The requires roughly log N comparisons. To find the correct place where to move
the hole, perform a binary search on the log N elements. This takes O(log log N) comparisons.
(b) Find a path of minimum children, stopping after log N − log log N levels. At this point, it is easy to
determine if the hole should be placed above or below the stopping point. If it goes below, then continue
6.14 The parent is at position
( 2)i d d+−
. The children are in positions (i − 1)d + 2, . . . , id + 1.
6.15 (a) O((M + d N) logd N).
6.16 Starting from the second most signficant digit in i, and going toward the least significant digit, branch left for
0s, and right for 1s.
6.17 (a) Place negative infinity as a root with the two heaps as subtrees. Then do a deleteMin.
(b) Place negative infinity as a root with the larger heap as the left subheap, and the smaller heap as the right
6.19
6.21 This theorem is true, and the proof is very much along the same lines as Exercise 4.20.
6.22 If elements are inserted in decreasing order, a leftist heap consisting of a chain of left children is formed. This
is the best because the right path length is minimized.
6.23 (a) If a decreaseKey is performed on a node that is very deep (very left), the time to percolate up would be
6.24 Lazy deletion in leftist heaps is discussed in the paper by Cheriton and Tarjan [10]. The general idea is that if
the root is marked deleted, then a preorder traversal of the heap is formed, and the frontier of marked nodes is
6.25 (a) The standard way to do this is to divide the work into passes. A new pass begins when the first element
reappears in a heap that is dequeued. The first pass takes roughly 2*1*(N/2) time units because there are N/2
6.26
6.28 This claim is also true, and the proof is similar in spirit to Exercise 4.20 or 6.21.
6.29 Yes. All the single operation estimates in Exercise 6.25 become amortized instead of worst-case, but by the
definition of amortized analysis, the sum of these estimates is a worst-case bound for the sequence.
6.30 Clearly the claim is true for k = 1. Suppose it is true for all values i = 1, 2, . . . , k. A Bk + 1 tree is formed by
attaching a Bk tree to the root of a Bk tree. Thus by induction, it contains a B0 through Bk − 1 tree, as well as the
6.33 This is established in Chapter 11.
6.38 Don’t keep the key values in the heap, but keep only the difference between the value of the key in a node
and the value of the parent’s key.