Solution of Question 6 from Exercise 5:

First, a definition: a rank-k star is a tree that has one root, and the root
has exactly k children which are the leaves.

The "bad" sequence of operations looks as follows:

1. A sequence of f(n) operations (f is some function of n but not of m) such
that in the end of the sequence, the heap consists of one rank-1 star, 
one rank-2 star, one rank-3 star, ..., one rank-(sqrt(n)) star.

2. Repeat the following two operations m/2 times, m being much larger than
f(n):
   (i) insert an element x of value smaller than all those in step 1.
   (ii) perform extract-min (thus removing x)

Each of the m/2 pairs of operations takes Omega(sqrt(n)) time, so if m>>n
then the average time per operation is sqrt(n). In fact, this is the highest
achievable. (We leave this as an exercise to the reader).

Now, we only need to show how to implement step 1: We'll show how to 
create a heap that has a rank-(sqrt(n)) star. This is enough, since we can 
apply a similar operation to the rest of the elements to get the rest of 
the stars.

Let's show a sequence of operations, that given k^2 elements, creates a
rank-k star. We call this sequence of operations A(k), and we build it
recursively. A(1),A(2), etc are obvious. Now, suppose we already have
A(k-1) and we wish to get A(k). A(k) is built as follows: First, run 
A(k-1) once to get a rank-(k-1) star. Now, you have k^2-(k-1) leaves, 
which is more than (k-1)^2, so you can run A(k-1) again to create another 
rank-(k-1) star. Now, perform extract-min so that both of the big stars 
merge. Now shave off some of the leaves (using decrease-key) and you got a 
rank-k star. This finishes the solution.