- 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*_{0},*B*_{1},...,*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.