Java Reference
In-Depth Information
Prove Theorem 21.1 by using a direct summation. Do the following.
a.
21.10
Show that there are 2 i nodes of height H - i
b.
Write the equation for the sum of the heights using part (a)
c.
Evaluate the sum in part (b)
Verify that the sum of the heights of all the nodes in a perfect binary
tree satisfies N - v ( N ), where v ( N ) is the number of 1s in N 's binary
representation.
21.11
Prove the bound in Exercise 21.11 by using an induction argument.
21.12
For heapsort, O ( N log N ) comparisons are used in the worst case. Derive
the leading term (i.e., decide whether it is N log N, 2 N log N , 3 N log N,
and so on).
21.13
Show that there are inputs that force every percDown in heapsort to go all
the way to a leaf. ( Hint: Work backward.)
21.14
Suppose that the binary heap is stored with the root at position r. Give for-
mulas for the locations of the children and parent of the node in position i .
21.15
Suppose that binary heaps are represented by explicit links. Give a simple
algorithm to find the tree node that is at implicit position i .
21.16
Suppose that binary heaps are represented by explicit links. Consider the
problem of merging binary heap lhs with rhs . Assume that both heaps are
full complete binary trees, containing 2 l - 1 and 2 r - 1 nodes, respectively.
a.
21.17
Give an O (log N ) algorithm to merge the two heaps if l = r .
b.
Give an O (log N ) algorithm to merge the two heaps if
lr
-
=
1
.
Give an O (log 2 N ) algorithm to merge the two heaps regardless of
l and r .
c.
A d-heap is an implicit data structure that is like a binary heap, except
that nodes have d children. A d -heap is thus shallower than a binary
heap, but finding the minimum child requires examining d children
instead of two children. Determine the running time (in terms of d and
N ) of the insertion and deleteMin operations for a d -heap.
21.18
A min-max heap is a data structure that supports both deleteMin and
deleteMax at logarithmic cost. The structure is identical to the binary
heap. The min-max heap-order property is that for any node X at even
depth, the key stored at X is the smallest in its subtree, whereas for any
node X at odd depth, the key stored at X is the largest in its subtree. The
root is at even depth. Do the following.
a.
21.19
Draw a possible min-max heap for the items 1, 2, 3, 4, 5, 6, 7, 8,
9, and 10. Note that there are many possible heaps.
b.
Determine how to find the minimum and maximum elements.
Search WWH ::




Custom Search