Suppose that a binary min-heap stores six elements with priorities 10, 20, 30, 40, 50, and 60 in its array $A$. What is the largest of these items that could be stored in $A[1]$? Draw the tree structure for a valid heap-ordered tree that places this item in $A[1]$, with each node of the tree labeled by the element it holds.
Solution: $A[1]$ has to be larger than at least two other items, in $A[3]$ and $A[4]$, so it can be at most $40$.
10
/ \
/ \
40 20
/ \ /
50 60 30
Draw the shape of the forest that you would get if you inserted nine elements into a Fibonacci heap and then performed a single delete-min operation. In your drawing, the children of each node should appear in left-to-right order in the order they were added as children (the first child on the left, etc).
Solution:
O
/|\
/ | \
O O O
| | \
O O O
|
O
In a hypercube network with $n$ vertices, the number of edges is $\tfrac{1}{2} n\log_2 n$. For instance, a cube network with $8$ vertices has $12 = \tfrac{1}{2} 8\log_2 8$ edges. Suppose that we are running Dijkstra's algorithm on such a network, using a $k$-ary heap for its priority queue. What should we choose as the value of $k$ in order to minimize the total time of Dijkstra's algorithm, and what is the total time of the algorithm for this choice? (Use $O$-notation for the time, simplified as much as possible. Your answer for the total time should only be a formula of $n$; it should not have $k$ as a separate variable in its formula.)
Solution: Choose $k$ to be proportional to $\log n$ (the exact constant of proportionality doesn't matter), giving running time $O\displaystyle\left(\frac{n\log^2 n}{\log\log n}\right)$.
Suppose we create a binary search tree on the three elements 10, 20, and 30 by inserting the three elements one at a time, without rebalancing, in a randomly chosen order. That is, we choose randomly one of the six permutations of 10, 20, and 30, and then, for each element in order, place it into the tree as a child of one of the previously placed tree nodes without changing the structure of the previous nodes. What is the probability that the resulting binary search tree can be labeled with ranks to make it a valid WAVL tree?
Solution: It is a WAVL tree if and only if the root is the middle element, 20, because otherwise the root would have one external node child (rank 0) and one child with distance 2 to an external node (rank at least 2), but these ranks of the children of the root are too far apart to be able to assign a rank to the root node. And element 20 is the root of the tree if and only if it is picked first, which happens with probability 1/3. So the probability that we get a tree that can be labeled as a WAVL tree is 1/3.