Heaps are arrays for which
a[k] <= a[2*k+1]
a[k] <= a[2*k+2]
for all k, counting
elements from 0. For the sake of comparison, non-existing elements are considered to be
infinite. The interesting property of a heap is that
is always its smallest element.
The strange invariant above is meant to be an efficient memory representation for a
tournament. The numbers below are k, not
3 4 5 6
7 8 9 10 11 12 13 14
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
In the tree above, each cell k is topping
. In an usual binary tournament
we see in sports, each cell is the winner over the two cells it tops, and we can trace the
winner down the tree to see all opponents s/he had. However, in many computer
applications of such tournaments, we do not need to trace the history of a winner. To be
more memory efficient, when a winner is promoted, we try to replace it by something else
at a lower level, and the rule becomes that a cell and the two cells it tops contain three
different items, but the top cell “wins” over the two topped cells.
If this heap invariant is protected at all time, index 0 is clearly the overall winner. The
simplest algorithmic way to remove it and find the “next” winner is to move some loser
(let’s say cell 30 in the diagram above) into the 0 position, and then percolate this new 0
down the tree, exchanging values, until the invariant is re-established. This is clearly
logarithmic on the total number of items in the tree. By iterating over all items, you get an
O(n log n) sort.
A nice feature of this sort is that you can efficiently insert new items while the sort is
going on, provided that the inserted items are not “better” than the last 0’th element you
extracted. This is especially useful in simulation contexts, where the tree holds all
incoming events, and the “win” condition means the smallest scheduled time. When an
event schedules other events for execution, they are scheduled into the future, so they
can easily go into the heap. So, a heap is a good structure for implementing schedulers
(this is what I used for my MIDI sequencer :-).
Various structures for implementing schedulers have been extensively studied, and heaps
are good for this, as they are reasonably speedy, the speed is almost constant, and the
worst case is not much different than the average case. However, there are other
representations which are more efficient overall, yet the worst cases might be terrible.