Suppose that you create a new Fibonacci heap, insert 65 elements into it, and then perform a single remove-min operation. How many trees will the resulting Fibonacci heap have, and how many nodes will be in each tree?
(Hint: if you perform a remove-min of a Fibonacci heap in which all trees have a single elements, what are the possible sizes of the resulting trees?)
Suppose that you have an implementation of a priority queue in which only three operations are allowed: create an empty heap, add an element, and remove-min. Your implementation takes actual time $O(1)$ to create an empty heap, and actual time $O(\log n)$ for the other two operations, where $n$ is the number of elements currently in the heap. Find a potential function $\Phi$ such that, with this potential function, the amortized time of an add-element operation is still $O(\log n)$ but the amortized time of a remove-min becomes $O(1)$.
For which values of $n$ does an $n$-element binary heap have an element with exactly one child, and where in the heap is that element and its child?
A hypercube graph of dimension $d$ has $2^d$ vertices and $d2^{d-1}$ edges. (For instance, the three-dimensional cube has 8 vertices and 12 edges.) Suppose that we are going to run Dijkstra's algorithm on this graph, using a $k$-ary heap for the priority queue. What would be the best choice of $k$ to use (the one that causes the algorithm to run as quickly as possible), and what would be the running time of the algorithm with this choice?
Both of your answers should be expressed as formulas involving $d$. The running time should use $O$-notation. The choice for $k$ should just be a formula, without $O$-notation, but you can simplify your answer to this part by omitting any constant factors from this formula, as they will not affect the $O$-notation for the running time.