Let \(T\) be a heap-ordered binary tree in which you know the identity of the tree root and can find the value of each tree node, and the identities of the left and right children of each tree node (if it has them) in constant time per operation. Describe an algorithm that takes as input \(T\) and a parameter \(k\), and uses a priority queue to find the \(k\) smallest values in \(T\) using \(O(k)\) priority queue operations. (Your priority queue can be a different structure than \(T\). You should not modify \(T\) itself. You do not need to choose which kind of priority queue to use. Your answer should clearly describe what elements you are storing in the priority queue, what their priorities are, and what operations you are performing on the priority queue.)
The lecture notes describe the worst case of Dijkstra's algorithm when there are \(m\) decrease-priority operations and \(n\) delete-min operations. Here, \(m\) is the number of edges in the input graph and \(n\) is the number of vertices. In this worst case, the optimal trade-off for a \(k\)-ary heap is to set \(k=m/n\), to make equal total times for each kind of operation. This choice leads to an overall running time of \(O(m (\log n)/\log(m/n))\). However, some heuristic analyses suggest that in many practical cases Dijkstra's algorithm may only perform \(O(n\log(m/n))\) decrease-priority operations, because many of the edges that it examines do not produce improved paths to their target vertex. When this turns out to be the number of decrease-priority operations, what is the optimal choice for \(k\) and the overall running time? (Don't forget that the algorithm must still do a constant amount of work for each edge in the graph, even if it doesn't do any priority queue operations for that edge.)
In a Fibonacci heap, suppose that we perform a sequence of operations, starting from any empty priority queue that includes only additions of elements and find-and-remove-min operations, but does not include any decrease-priority operations. Is it possible for the resulting Fibonacci heap to include a tree with exactly five nodes in it? Explain why (by finding a sequence of operations of this type that produces a five-node tree) or why not.
Suppose that a set \(S\) is represented as a bitmap, as described in the lectures from week 3. Describe how to perform a find-and-remove-minimum-element operation on \(S\), using a constant number of the bitwise binary operations discussed in that week's lectures. As in that week's exercises, you may assume that the dictionary set2element has already been constructed and that searching this dictionary is one of the allowed operations.