Java Reference
In-Depth Information
priority=8, description=Water plants
priority=9, description=Clean coffee maker
priority=10, description=Remove pencil sharpener
shavings
S
ELF
C
HECK
15.
The software that controls the events in a user interface keeps the events
in a data structure. Whenever an event such as a mouse move or repaint
request occurs, the event is added. Events are retrieved according to
their importance. What abstract data type is appropriate for this
application?
16.
Could we store a binary search tree in an array so that we can quickly
locate the children by looking at array locations
2 * index
and
2 *
index + 1
?
16.10 The Heapsort Algorithm
Heaps are not only useful for implementing priority queues, they also give rise to an
efficient sorting algorithm, heapsort. In its simplest form, the algorithm works as
follows. First insert all elements to be sorted into the heap, then keep extracting the
minimum.
The heapsort algorithm is based on inserting elements into a heap and removing
them in sorted order.
This algorithm is an O(n log(n)) algorithm: each insertion and removal is O(log(n)),
and these steps are repeated n times, once for each element in the sequence that is to
be sorted.
Heapsort is an O(n log(n)) algorithm.
The algorithm can be made a bit more efficient. Rather than inserting the elements
one at a time, we will start with a sequence of values in an array. Of course, that array
does not represent a heap. We will use the procedure of Ȓfixing the heapȒ that you
encountered in the preceding section as part of the element removal algorithm.
