Suppose that binary heaps are represented using explicit links. Consider the problemof

Can both insert and findMin be implemented in constant time?

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.

3 Show the result of performing three deleteMin operations in the heap of the previous exercise.

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

Rewrite the BinaryHeap insert method by placing a reference to the inserted item in position 0.

How many nodes are in the large heap in Figure 6.13?

a. Prove that for binary heaps, buildHeap does at most 2N2 comparisons between elements. b. Show that a heap of eight elements can be constructed in eight comparisons between heap elements. c. Give an algorithm to build a binary heap in 13 8 N + O(logN) element comparisons.

Show the following regarding the maximum item in the heap: a. It must be at one of the leaves. b. There are exactly N/2 leaves. c. Every leaf must be examined to find it.

Show that the expected depth of the kth smallest element in a large complete heap (you may assume N = 2k 1) is bounded by log k.

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 arbitrary item X in a binary heap using at most roughly 3N/4 comparisons.

1 Propose an algorithm to insert M nodes into a binary heap on N elements in O(M + logN log logN) time. Prove your time bound.

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.Compare the running time of both algorithms for sorted, reverse-ordered, and random inputs.

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?

If a d-heap is stored as an array, for an entry located in position i, where are the parents and children?

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?

Suppose that binary heaps are represented using explicit links. Give a simple algorithm to find the tree node that is at implicit position i.

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.

8 A min-max heap is a data structure that supports both deleteMin and deleteMax in O(logN) per operation. The structure is identical to a binary heap, but the heaporder property is that for any node, X, at even depth, the element stored at X is smaller than the parent but larger than the grandparent (where this makes sense), and for any node X at odd depth, the element stored at X is larger than the parent but smaller than the grandparent. See Figure 6.57. a. How do we find the minimum and maximum elements? b. Give an algorithm to insert a new node into the min-max heap. c. Give an algorithm to perform deleteMin and deleteMax. d. Can you build a min-max heap in linear time? e. Suppose we would like to support deleteMin, deleteMax, and merge. Propose a data structure to support all operations in O(logN) time.

Merge the two leftist heaps in Figure 6.58.

Show the result of inserting keys 1 to 15 in order into an initially empty leftist heap.

Prove or disprove: A perfectly balanced tree forms if keys 1 to 2k 1 are inserted in order into an initially empty leftist heap

Give an example of input that generates the best leftist heap.

a. Can leftist heaps efficiently support decreaseKey? b. What changes, if any (if possible), are required to do this?

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))

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?

Merge the two skew heaps in Figure 6.58.

Show the result of inserting keys 1 to 15 in order into a skew heap

Prove or disprove: A perfectly balanced tree forms if the keys 1 to 2k1 are inserted in order into an initially empty skew heap.

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?

Prove that a binomial tree Bk has binomial trees B0, B1, ... , Bk1 as children of the root.

Prove that a binomial tree of height k has k d  nodes at depth d.

Merge the two binomial queues in Figure 6.59.

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.

4 Write an efficient routine to perform insert using binomial queues. Do not call merge.

For the binomial queue: a. Modify the merge routine to terminate merging if there are no trees left in H2 and the carry tree is null. b. Modify the merge so that the smaller tree is always merged into the larger.

Suppose we extend binomial queues to allow at most two trees of the same height per structure. Can we obtain O(1) worst-case time for insertion while retaining O(logN) for the other operations?

Suppose you have a number of boxes, each of which can hold total weight C and items i1, i2, i3, ... , iN, which weigh w1, w2, w3, ... , wN, respectively. The object is to pack all the items without placing more weight in any box than its capacity and using as few boxes as possible. For instance, if C = 5, and the items have weights 2, 2, 3, 3, then we can solve the problem with two boxes. In general, this problem is very hard, and no efficient solution is known. Write programs to implement efficiently the following approximation strategies: a. Place the weight in the first box for which it fits (creating a new box if there is no box with enough room). (This strategy and all that follow would give three boxes, which is suboptimal.) b. Place the weight in the box with the most room for it. c. Place the weight in the most filled box that can accept it without overflowing. d. Are any of these strategies enhanced by presorting the items by weight?

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).

Which of the two selection algorithms has the better time bound?