Suppose that, starting from an empty Fibonacci heap, we perform a sequence of $n$ insertions followed by a single delete-min operation. Describe, as a function of $n$, the numbers of nodes in each tree of the resulting heap.
(Hint: consider the binary representation of $n$. The answer will not depend on the priorities of the elements nor on the order in which trees are merged in the delete-min operation.)
Recall that, in any Fibonacci heap, the $i$th child of any node (for $i=1,2,3,\dots$ in sorted order by the times at which the children became children of that node) must have degree at least $\max(0,i-2)$.
Suppose that a tree $T$ obeys this property and that its root node has three children. What is the smallest possible total number of nodes in $T$?
Find a sequence of Fibonacci heap operations (insert an item with priority $x$, decrease the priority of an item from $x$ to $y$, or delete-min) such that performing these operations starting from an empty heap will construct a tree $T$ whose root has three children and whose total number of nodes is your answer to part (a).
(Hint: you will need to form a larger tree and then reduce its size by decrease-priority operations. It is ok for the heap to contain more than one tree as long as at least one of its trees solves the problem.)
The solution to homework 1 problem 1 can be used to find a potential function such that, for a binary heap, the amortized time for an insertion operation is still $O(\log n)$ but the amortized time for a delete-min operation is $O(1)$.
With this potential function, what would be the amortized time to initialize a new binary heap with $n$ elements?
Can this idea be used to reduce the time bound for Dijkstra's algorithm using binary heaps? Explain how if yes, or why not if no.