Solutions To Homework 8

A heap T with seven distinct elements such that a pre-order traversal of T yields the elements of T in sorted order exists. For example, we can construct such a tree by doing insertions into an initially empty heap as follows:

insert 1, 2, 5, 3, 4, 6, 7 in that order.

There exists a heap storing seven distinct elements such that post order traversal of T yields the elements of T in sorted order.

To construct such a tree, we insert the following elements in that order.

-1,3,0,5,4,2,1.

When listed in post order, this produces the sequence : 5,4,3,2,1,0,-1

We can see that the sum of log 1 to log n is the same as log (1.2.3...n) which is nothing but log(n!). Using Stirlings approximation we can show that n! >= n^n. ( Please see page no. 711 of the text book ) for strilings approximation). So,

log(n!) >= log(n^n) = nlogn.

Hence the result.

The following sequence of steps delete the key 16.

1) Swap 16 with 4 ( i.e root )
2) Delete 16 by swapping with the last element (8) and push 8 down.
3) Bubble 4 up.

To replace 5 with 18, we follow the following steps

1) Find key 5 and overwrite it with 18.
2) Since 18 is larger than the root (4) and larger than its children ( 15,9), bubble it downwards.

To report all the keys smaller than some query key x we would first compare the root of the heap with x. If it is larger than x then the algorithm terminates else we report it and perform the same operation on both its children recursively.

We can see that this algorithm will perform k comparisons at least. But at each node that it reports it may perform 2 comparisons extra with the children of that node which may be larger than x. This means that it will perform upto 3k comparisons at most which is O(k).