Chapter 8

How long would it take to remove the $\lceil \log n\rceil$ smallest elements from a heap that contains $n$ entries using the removeMin() operation?

Show that, given only the less-than operator ( $<$ ) and the boolean operators and $(\mathrm{\&}\mathrm{\&}),$ or $(\Vert ),$ and not $(!),$ it is possible to implement all of the other comparators: $>,<=,>=,==$

An airport is developing a computer simulation of air-traffic control that handles events such as landings and takeoffs. Each event has a time-stamp that denotes the time when the event occurs. The simulation program needs to efficiently perform the following two fundamental operations: • Insert an event with a given time-stamp (that is, add a future event) • Extract the event with smallest time-stamp (that is, determine the next event to process) Which data structure should be used for the above operations? Why?

Although it is correct to use a "reverse" comparator with our priority queue ADT so that we retrieve and remove an element with the maximum key each time, it is confusing to have an element with the maximum key returned by a function named "removeMin." Write a short adapter class that can take any priority queue $P$ and an associated comparator $C$ and implement a priority queue that concentrates on the element with the maximum key, using functions with names like removeMax. (Hint: Define a new comparator $C^{\prime }$ in terms of $C$.)

Illustrate the performance of the selection-sort algorithm on the following input sequence: (22,15,36,44,10,3,9,13,29,25).

Give an example of a worst-case sequence with $n$ elements for insertionsort, and show that insertion-sort runs in $\mathrm{\Omega }\left(n^2\right)$ time on such a sequence.

Illustrate the performance of the heap-sort algorithm on the following input sequence: (2,5,16,4,10,23,39,18,26,15)

Let $T$ be a complete binary tree such that node $v$ stores the key-entry pairs $(f(v),0),$ where $f(v)$ is the level number of $v.$ Is tree $T$ a heap? Why or why not?

Let $H$ be a heap storing 15 entries using the vector representation of a complete binary tree. What is the sequence of indices of the vector that are visited in a preorder traversal of $H?$ What about an inorder traversal of $H?$ What about a postorder traversal of $H?$

Show that the sum $\sum _{i=1}^n\log i,$ which appears in the analysis of heap-sort, is $\mathrm{\Omega }(n\log n)$.