Advanced Algorithms
Describe the structure of an ordinary heap, and document the costs associated with
the following operations.
(a) Create a heap from n items where the items are all available at once but are
initially in a random order.
(b) Remove the top (i.e. smallest) value stored in the heap.
(c) Given a pointer to an arbitrary item in the heap, re-instate the heap property
after the key associated with that single item is decreased in value.
(d) Form a new heap whose elements are all those that are present in two other
heaps (which may be destroyed in the combining process if that helps).
You are not expected to give detailed accounts of the algorithms involved.
[6 marks]
Now explain the structure of a Binomial Heap and compare, with some explanation
of your claims, the costs incurred in the same set of operations if Binomial rather
than ordinary heaps were to be used. [14 marks]