Define a "factorial tree" to be one in which the number of children of a node at the ith level is (i+1), so there are i! nodes at the ith level. That is, the root has two children, each of these has three children, etc.

(1) How many levels are there in a factorial tree with n nodes? Use O-notation. (Hint: Stirling's formula.)

(2) Suppose that we form a heap-like data structure using a factorial tree in place of the complete binary tree used by a binary heap. What would be the running time for a delete-min operation? For a decrease-key operation?

(3) If we use a factorial-tree heap in Dijkstra's algorithm, on graphs with n vertices and m edges, what is the running time? For what values of m would this running time be faster than for a binary heap?