6.1 Can both insert and findMin be implemented in constant time? - Get solution
6.2 a. Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time, into an initially empty binary heap.
b. Show the result of using the linear-time algorithm to build a binary heap using the same input. - Get solution
6.3 Show the result of performing three deleteMin operations in the heap of the previous exercise. - Get solution
6.4 A complete binary tree of N elements uses array positions 1 to N. Suppose we try
to use an array representation of a binary tree that is not complete. Determine how
large the array must be for the following:
a. a binary tree that has two extra levels (that is, it is very slightly unbalanced)
b. a binary tree that has a deepest node at depth 2 logN
c. a binary tree that has a deepest node at depth 4.1 logN
d. the worst-case binary tree - Get solution
6.5 Rewrite the BinaryHeap insert method by placing a reference to the inserted item in
position 0. - Get solution
6.6 How many nodes are in the large heap in Figure 6.13? - Get solution
6.10 a. Give an algorithm to find all nodes less than some value, X, in a binary heap.
Your algorithm should run in O(K), where K is the number of nodes output.
b. Does your algorithm extend to any of the other heap structures discussed in this chapter?
c. Give an algorithm that finds an - Get solution
6.12 Write a program to take N elements and do the following:
a. Insert them into a heap one by one.
b. Build a heap in linear time. - Get solution
Compare the running time of both algorithms for sorted, reverse-ordered, and
random inputs.
6.13 Each deleteMin operation uses 2 logN comparisons in the worst case.
a. Propose a scheme so that the deleteMin operation uses only logN + log logN +
O(1) comparisons between elements. This need not imply less data movement.
b. Extend your scheme in part (a) so that only logN + log log logN + O(1)
comparisons are performed.
c. How far can you take this idea?
d. Do the savings in comparisons compensate for the increased complexity of your algorithm? - Get solution
6.14 If a d-heap is stored as an array, for an entry located in position i, where are the parents and children? - Get solution
6.15 Suppose we need to perform M percolateUps and N deleteMins on a d-heap that initially has N elements.
a. What is the total running time of all operations in terms of M, N, and d?
b. If d = 2, what is the running time of all heap operations?
c. If d = (N), what is the total running time?
d. What choice of d minimizes the total running time? - Get solution
6.16 Suppose that binary heaps are represented using explicit links. Give a simple algorithm to find the tree node that is at implicit position i. - Get solution
6.17 Suppose that binary heaps are represented using explicit links. Consider the problem of merging binary heap lhs with rhs. Assume both heaps are perfect binary
trees, containing 2l − 1 and 2r − 1 nodes, respectively.
a. Give an O(logN) algorithm to merge the two heaps if l = r.
b. Give an O(logN) algorithm to merge the two heaps if |l − r| = 1.
c. Give an O(log2 N) algorithm to merge the two heaps regardless of l and r. - Get solution
6.19 Merge the two leftist heaps in Figure 6.58. - Get solution
6.20 Show the result of inserting keys 1 to 15 in order into an initially empty leftist heap. - Get solution
6.21 Prove or disprove: A perfectly balanced tree forms if keys 1 to 2k − 1 are inserted in order into an initially empty leftist heap. - Get solution
6.22 Give an example of input that generates the best leftist heap. - Get solution
6.23 a. Can leftist heaps efficiently support decreaseKey?
b. What changes, if any (if possible), are required to do this? - Get solution
6.24 One way to delete nodes from a known position in a leftist heap is to use a lazy strategy. To delete a node, merely mark it deleted. When a findMin or deleteMin is performed, there is a potential problem if the root is marked deleted, since then the node has to be actually deleted and the real minimum needs to be found, which may involve deleting other marked nodes. In this strategy, deletes cost one unit, but the cost of a deleteMin or findMin depends on the number of nodes that are marked deleted. Suppose that after a deleteMin or findMin there are k fewer marked nodes than before the operation.
a. Show how to perform the deleteMin in O(k logN) time.
b. Propose an implementation, with an analysis to show that the time to perform the deleteMin is O(k log(2N/k)). - Get solution
6.25 We can perform buildHeap in linear time for leftist heaps by considering each
element as a one-node leftist heap, placing all these heaps on a queue, and performing
the following step: Until only one heap is on the queue, dequeue two
heaps, merge them, and enqueue the result.
a. Prove that this algorithm is O(N) in the worst case.
b. Why might this algorithm be preferable to the algorithm described in the text? - Get solution
6.26 Merge the two skew heaps in Figure 6.58. - Get solution
6.27 Show the result of inserting keys 1 to 15 in order into a skew heap. - Get solution
6.28 Prove or disprove: A perfectly balanced tree forms if the keys 1 to 2k−1 are inserted in order into an initially empty skew heap. - Get solution
6.29 A skew heap of N elements can be built using the standard binary heap algorithm.
Can we use the same merging strategy described in Exercise 6.25 for skew heaps to get an O(N) running time? - Get solution
6.30 Prove that a binomial tree Bk has binomial trees B0, B1, . . . , Bk−1 as children of the
root. - Get solution
6.31 Prove that a binomial tree of height k has kd nodes at depth d. - Get solution
6.32 Merge the two binomial queues in Figure 6.59. - Get solution
6.33 a. Show that N inserts into an initially empty binomial queue takes O(N) time in the worst case.
b. Give an algorithm to build a binomial queue of N elements, using at most N−1 comparisons between elements.
c. Propose an algorithm to insert M nodes into a binomial queue of N elements in O(M + logN) worst-case time. Prove your bound. - Get solution
6.38 Suppose we want to add the decreaseAllKeys() operation to the heap repertoire.
The result of this operation is that all keys in the heap have their value decreased by an amount. For the heap implementation of your choice, explain the necessary modifications so that all other operations retain their running times and decreaseAllKeys runs in O(1). - Get solution
6.39 Which of the two selection algorithms has the better time bound? - Get solution
