1. I'm looking for something like the following:

    Q = new priority queue for the elements of X, prioritized by sort
    key
    while Q is not empty:
        find and remove the element x of Q with minimum key
        output x

There are a lot of other possibilities (e.g. to collect the elements
into a list and then to return it instead of using an output statement)
but the important parts are that it should include a statement where the
priority queue is initialized and a statement that finds and removes the
minimum element (or these can be separate operations).


2. Let Phi = n log_2 n, where n is the number of elements currently in
the tree.

Then when an element is inserted, the actual time is O(log n), and Phi
changes from n log_2 n to (n+1) log_2 (n+1); the difference between
these two values is O(log n). So the total amortized time for an
insertion is O(log n) + O(log n).

When an element is deleted, Phi changes from (n+1) log_2 (n+1) to
n log_2 n; the difference is < -log_2 n.  By choosing a large enough
constant of proportionality C in the formula amortized time = actual
time + C*(difference in potential) we can make this negative log cancel
the O(log n) actual time of the deletion, leaving zero (which is O(1)).


3. After making k^2 insertions into the modified dynamic array, the
sequence of resizes we will have made will be 1, 4, 9, ..., k^2; the sum
of these sizes is Theta(k^3). Therefore, the average time spent
resizing, per insertion, is Theta(k^3 / k^2) = Theta(k).  Rewriting this
with n = k^2 being the number of insertions, the average time per
insertion is Theta(sqrt n). It's not possible for the amortized time per
insertion to be smaller than this, because the sum of amortized times is
always greater than or equal to the sum of actual times.