6.4 Problems

1.

Show the result of inserting 10, 5, 1, 17, 20, 15, 6, 4, 2, one at a time, into an initially empty binary heap. For the same input, show the result of building the heap by the linear time algorithm discussed.

2.

Design an algorithm to find all nodes less than some value, x, in a binary heap. Your algorithm should run in O (m), worst-case time, where m is the number of nodes output.

3.

A min-max heap is a data structure that supports both deletemin and deletemax in O ( log n) worst-case time. The structure is identical to a binary heap, but the heap order property is that, for any node x, at even depth, the key stored at x is the smallest in its subtree, and for any node x at odd depth, the key stored at x is the largest in its subtree.

(a)

How do we find minimum and maximum elements

(b)

Present an algorithm to insert a new node into the min-max heap

(c)

Give an algorithm to perform deletemin and deletemax

4.

Prove that a binomial tree B_k has binomial trees B₀, B₁,..., B_{k - 1} as children of the root.

5.

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

6.

Present an algorithm to insert m nodes into a binomial queue of n elements in O(m + log n) worst-case time. Prove your bound.

7.

It is required to increment the value of the roots of all binomial trees in a binomial queue. What is the worst-case running time of this in terms of the number of elements in the binomial queue.

8.

Design an algorithm to search for an element in a binary heap. What is the worst-case complexity of your algorithm. Can you use the heap property to speedup the search process?

9.

Prove that a binomial queue with n items has at most log n binomial trees, the largest of which contains 2^{log n} items.

10.

How do you implement the following operations in a binary heap?

• Decrease the key at some position
• Increase the key at some position
• Remove element at some position

11.

What is the worstcase complexity of each problem below, given a binomial queue with n elements? Explain with reason or example in each case.

(a)

Find the second smallest element

(b)

Find the second largest element

12.

Consider lazy binomial queues where the merge operation is lazy and it is left to the deletemin operation to convert the lazy binomial queue into a binomial queue in standard form. Obviously, the merge operation is O(1), but the deletemin operation is not worst case O(log n) anymore. However, show that deletemin is still O(log n) in amortized time.