Practice Problem Set 5
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.)
Solution: Create a priority queue \(Q\) of nodes in \(T\), prioritized by value, initially containing only the root of \(T\). Then repeat \(k\) times:
Find and remove the minimum-value node \(x\) in \(Q\).
Add to \(Q\) the children of \(x\).
Output \(x\).
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.)
Solution: As before, the optimal tradeoff occurs when setting \(k\) the total time for decrease-priority operations and the time for delete-min operations is equal: otherwise, one of these two times will be larger than it would be when they are equal, and will cause the total time for both operations to be larger. The equality of times, under the given assumption on the number of decrease-priority operations, can be expressed as \[n\log\frac{m}{n}\log_k n=nk\log_k n.\] Cancelling equal terms gives us \[\log\frac{m}{n}=k,\] giving us the optimal choice of \(k\). Plugging this into the time analysis for the whole algorithm (not just the data structure operations), using the identity \(\log_a b = (\log a)/(\log b)\), and reordering the expression to make it more obvious what the argument of the log is, gives us total time \[O\left(m+n\frac{\log n}{\log\log m/n}\log\frac{m}{n}\right).\]
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.
Solution: Without decrease-priority operations, we never remove a child of a node: all we do is merge trees with equal degrees, and promote all the children of the minimum root to be roots. These two operations preserve the invariant that the number of nodes in a subtree with degree \(i\) is exactly \(2^i\). Because five is not a power of two, a five-node tree cannot appear.
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.
Solution (as usual with bit operations, there are many equivalent variations, and if I were grading these I wouldn't require the exception checking):
if not S: raise Exception("priority queue is empty") b = S &~ (S-1) S &=~ b return set2element[b]