|
![](/i/fill.gif) |
Ever since I read that book I got for Christmas, I've been carrying
around this implementation of a minimum-heap ("min-heap") in my head.
The design always seemed quite neat to me, and it seemed to have
impressive properties. But today I sat down to actually put those
properties to the test.
I've written a short program that randomly inserts and deletes elements
from the heap and measures how badly unbalanced the heap tree is. As per
my expectations, it seems that inserting produces nicely balanced trees.
Somewhat surprisingly, I have discovered that deletions can produce
arbitrarily unbalanced trees.
The actual algorithm can be succinctly described thus:
data Heap x = Node x (Heap x) (Heap x) | Empty
insert x' (Node x h0 h1) = Node (min x x') (insert (max x x') h1) h0
insert x' (Empty ) = Node x' Empty Empty
get_min (Node x _ _) = x
get_min (Empty ) = error "empty heap"
delete_min (Node _ h0 h1) = merge h0 h1
delete_min (Empty ) = error "empty heap"
merge Empty h1 = h1
merge h0 Empty = h0
merge h0 h1 =
if get_min h0 < get_min h1
then Node (get_min h0) h1 (delete_min h0)
else Node (get_min h1) h0 (delete_min h1)
For those who do not grok Haskell, let me summarise thus:
1. A heap is simply a binary tree where every node contains one datum
and has between 0 and 2 children.
2. Insert:
- Inserting into an empty heap yields a trivial 1-node tree.
- Inserting into a non-empty heap proceeds as follows:
A. Construct a new tree node containing the smaller of the existing
root element and the new element to be inserted.
B. The right child of the new node is the left child of the original
root node.
C. The left child of the new node is constructed by recursively
inserting the larger of the two elements into the previous right subtree.
3. Get minimum element: Just return the datum from the root node of the
tree.
4. Delete minimum element: Just take the two subtrees of the root node
and heap-merge them.
5. Heap merge:
- Merging a heap with an empty heap is no-op.
- To marge two non-empty heaps:
A. Determine which heap has the lowest datum in its root node.
B. Put the lowest datum into the new root node, and recursively
delete it from the subtree you got it from.
It might just be me, but I can't help noticing how the English
description is vastly more wordy yet less precise than the source code.
But anyway...
Notice how an insertion always swaps the two subtrees, and how it always
inserts into the (old) right subtree [which becomes the new left
subtree]. In this way, the left subtree of any node is always the larger
than or the same size as the corresponding right subtree. In other
words, insertions leave the tree balanced.
Notice also how a deletion (or rather, a merge) always puts the subtree
you just deleted from as the right subtree, reinforcing the same
invariant. The left subtree can never be smaller than the right subtree.
However, they *can* be wildly different sizes. If, by some misfortune,
it happens that you have a node where *all* the elements in one subtree
are strictly less than *all* of the elements in the other subtree, then
deleting from this heap will cause it to become more and more
unbalanced. And no amount of swapping subtrees around is going to fix that.
We have that deletion leaves the heap in a state where a subsequent
insertion will definitely insert into the smaller subtree, which is
good. In other words, inserting will always bring the tree back towards
being balanced again. But that still doesn't change the fact that, for
sufficiently pathological cases, deletions can make the tree unbalanced
to an unlimited degree.
Since a heap is (quite deliberately) only *partially* sorted, there's
nothing to prevent this kind of thing from happening. The only way we're
gonna fix this is to start moving stuff from one subtree to the other if
it gets too unbalanced. But can we detect this condition in a way that
doesn't slow the whole thing down too much?
Insert has the invariant that the sizes of the left and right subtrees
are related. At all times, we have either L = R or L = R + 1. The
constant swapping of the two subtrees mean that they both fill at an
equal rate.
Insert propagates items from the top downwards. Which way the item
propagates is down to the insertion function. But deletion moves items
up to the top. Which side the item comes from depends on which item is
the lowest, which the deletion function has no control over. Hence the
problem.
Deleting from the left subtree causes it to become the right subtree. If
we always deleted from the left, the tree would always remain balanced,
and there would be no problem. Deleting from the right subtree, however,
can unbalance the tree.
Now obviously, if the lowest element is in the right subtree, then it's
in the right subtree. There's nothing we can do about that. But this
(and only this) condition looks like a suitable signal that some
rebalancing is required. The question is, what do we do to rebalance?
One obvious possibility is to completely rebuild the entire subtree at
this moment. This operation has O(n log n) complexity, and is obviously
ludicrously expensive to do on (potentially) every single delete operation.
A better possibility is to move one element from the left subtree into
the right subtree if it's going to become too small. Actually to do this
reliably requires that we know whether L = R or L = R + 1. In the former
case, we do nothing, and in the latter case we rebalance by moving a
single element across. Here's the code:
data Balance = Equal | Unequal
invert Equal = Unequal
invert Unequal = Equal
data Heap x = Node Balance x (Heap x) Heap x) | Empty
insert x' (Node b x h0 h1) = Node (invert b) (min x x') (insert (max
x x') h1) h0
insert x' (Empty ) = Node Equal x Empty Empty
get_min (Node _ x _ _) = x
get_min (Empty ) = error "empty heap"
delete_min (Node x _ h0 h1) = merge b h0 h1
delete_min (Empty ) = error "empty heap"
merge _ Empty h1 = h1
merge _ h0 Empty = h0
merge _ h0 h1 =
if get_min h0 < get_min h1
then Node (invert b) (get_min h0) h1 (delete_min h0)
else rebalance b (get_min h1) h0 (delete_min h1)
rebalance Equal x h0 h1 = Node Unequal x h0 h1
rebalance Unequal x h0 h1 = let x' = get_min h0 in Node Equal x
(delete_min h0) (insert x' h1)
Here the functions "invert", "merge" and "rebalance" are private
functions not accessible to external clients.
I've run this code through my simulator, and after many minutes of
number crunching it has failed to produce one single unbalanced tree.
This of course is not proof, but it shows at least that this structure
works somewhat better than the original. (And for very little cost in
either code size of run-time complexity.)
Unfortunately, because we've added a new invariant to the data structure
(namely that the balance factor is always exactly 0 or -1), we lose the
ability to cheaply merge two heaps. (In the old version, this was
already a very cheap way to make an arbitrarily unbalanced tree; just
merge a size-1 tree with a size-1000 tree and watch how lopsided it now
is!) You would now be forced to do some kind of elaborate rebalancing
procedure to restore the new invariant on the subtree sizes.
Post a reply to this message
|
![](/i/fill.gif) |