Heaps
A heap is a binary tree with a special ordering imposed upon it.
Every item or node in the heap has a priority associated with it,
and the priority determines where a node as allowed to be, with
respect to the other nodes.
There is a special node, called the "root", which forms the base of the
heap. Every node except for the root has a "parent", which is directly
above it. If A is the parent of B, then B is a child of A. Every node has
zero, one, or two children, never more.
The ordering rule is very simple. For a "Min-Heap", the most common form,
the only rule is that no node's priority may be less than its parent's
priority. For a "Max-Heap", no child may be greater than its parent.
Remember that the usual scheme is to have numerically low priorities
correspond with high degrees of importance or urgency, so in a Min-Heap,
the most important node is at the top.
That is it. No global rules, just every node >= its parent.
Here is a perfectly healthy and happy heap. Observe that it follows the rules.
Even though a little number like 8 is way down at the 4th level, when something
big like 52 is at the second level, the rule "every node is >= its parent"
is always strictly obeyed. Nothing else matters.
The other thing that makes heaps interesting is that they happily live inside
arrays. If you have a heap with up to N items in it, then an array with indexes
ranging from [1] to [N] is just perfect for representing it, contents plus structure.
(C and C++ insist that arrays start at [0], so you need N+1 elements). The plan is
that the root is always at index [1]. For any node at index [X], its parent is at
index [X/2], and its (up to) two children are at indices [2X] and [2X+1]. Here is the
example heap from the above diagram living in an array:
1: 3
|
2: 6
|
3: 52
|
4: 49
|
5: 7
|
6: 75
|
7: 54
|
8: 54
|
9: 50
|
10: 8
|
11: 99
|
12: 77
|
13: 99
|
14: 60
|
15: 112
|
16: 88
|
17: 62
|
18: 51
|
Laid out like that, you can easily see that a heap isn't properly sorted in the normal
sense, but it is a little bit sorted. Making a heap is half way to sorting an array.
I think it is easier to understand a heap if you draw the array differently. The following
shows exactly the same array, making exactly the same heap, but it manages to show
both layouts at the same time.
1: 3
2: 6
3: 52
4: 49
5: 7
6: 75
7: 54
8: 54
9: 50
10: 8
11: 99
12: 77
13: 99
14: 60
15: 112
16: 88
17: 62
18: 51
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
There are only three things you can reasonably do with a heap: remove a node from it,
add a node to it, or reposition a node that is already in it.
The Three Operations
The object of happy heap manipulation is to minimise disruption. Always do everything
in the easiest possible way.
Insertion
If you want to insert a new piece of data with minimal disruption, just look at the above
diagram, and you'll see that putting it in the first free space (in this case index [19])
is the only option that doesn't require moving around items that are already properly
in place. Of course, putting new data at position [19] might violate the one heap rule,
but that is easy to fix. Let's call the value we are inserting "XX", and see what the heap
looks like if we put it at the first free space:
1: 3
2: 6
3: 52
4: 49
5: 7
6: 75
7: 54
8: 54
9: 50
10: 8
11: 99
12: 77
13: 99
14: 60
15: 112
16: 88
17: 62
18: 51
19: XX
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |
The only rule for a heap is in terms of a node's relationship with its parent,
so we'll look at how XX (at index [19]) relates to its parent (at index [9]).
(Why [9]? The parent of [N] is at [N/2], and of course these are integer operations,
19/2 is 9). The Va;ue in the parent node is 50.
There are only two cases:
- XX >= 50; the new node is not less than its parent. The heap rule is satisfied,
so there is nothing to do. Just leave the new piece of data where it is.
- XX < 50; the new node is less than its parent. The heap rule is violated,
so we must do something. What can we do? XX and its parent are out of order, so swap
them around. Swap item [19] with item [9], then continue the check. XX might still
be < its parent even at the new position, so keep comparing and swapping if out
of order.
Depending on how small XX is, it could work its way all the way to the top of the tree.
This diagram shows what could happen. XX is added, and keeps getting compared with its
parent, swapping if necessary. As soon as the item finds itself in a valid position
(either >= its parent, or at the root of the heap), the procedure stops.
Here is the insertion procedure:
void insert(data xx)
{ N+=1;
heap[N]=xx;
fix_upwards(N); }
void fix_upwards(int position)
{ while (true)
{ if (position==1) break;
int parent=position/2;
if (heap[position].priority >= heap[parent].priority) break;
swap(heap[position], heap[parent]);
position=parent; } }
Removal
Of course, we could remove any item from the heap, but we want to keep it
simple. The only thing we are likely to want to remove is the top thing. Heaps
have no overall ordering, the only overall position we can rely on is that
the smallest (most important) thing will be at the top. The top is the only item that
matters, so the top is the only one we are likely to really want to get our
hands on.
Removing the top item would completely destroy the heap, so we'd like to avoid it.
In fact, the only item that is easy to remove is the very last one, the 51 at position [18].
So we make a compromise. We'll swap the one we want (item [1]) with the one that is easy to
remove (item [18]), then remove the easy one.
This results in the following heap configuration (ignore the coloured arrows for now).
We've got the 3 from the top, and put the 51 in its place. Of course, the heap is not
healthy any more, it has a bif number at the top, but the repeairs are quite easy.
The 3, which appears in ghostly grey at the end, isn't really in the heap any more. Just
subtracting 1 from N tells us not to look at that item. The only thing that has moved is
the 51 now at the top. As the heap was OK before the move, the only possible problem is
that the 51 (at index [1]) might have a child (at indices [2] and [3]) that is smaller
than it. So what we do is find out whether that really is the case. If it isn't, then
the heap is still good, there is no fixing to do. If the root is not the smallest any
more, then we need to do something.
If the item now at the top isn't the most important in the whole heap, then one of
its direct children (6 or 52) must be. It is easy to find out which (compare them and
take the smallest). So the new, out-of-place, root is swapped with its smallest (most
importand) child. After the swap, it still might be out of position, so we continue
the checking. Keep track of where the out-of-place item is, if it is > any of
its children, swap it.
This diagram shows the procedure. The read arrows show the progress of the displaced
51, being compared with its children and swapped with the smallest. The green arrows
show the two children being compared to see which wins.
Here is the whole procedure for taking the most important item out of the heap, then
repairing the heap.
data remove(void)
{ swap(heap[1], heap[N]);
N-=1;
fix_downwards(1);
return heap[N+1]; }
void fix_downwards(int position)
{ while (true)
{ int left_child = position*2;
int right_child = left_child+1;
if (left_child > N) break;
int best_child = left_child;
if (right_child <= N)
{ if (heap[right_child].priority < heap[left_child].priority)
best_child = right_child; }
if (heap[position].priority < heap[best_child].priority) break;
swap(heap[position], heap[best_child]);
position = best_child; } }
Priority Change
Happily, there is nothing to think about here. If the priority of an item already
in the heap is changed, there are only two possibilities. If it gets less important,
then it might need to be replaced by one of its children. If it gets more important
then it might need to replace its own parent. We have already worked out how to
do both of those things:
void adjust(int position, int new_priority)
{ int old_priority = heap[position].priority;
heap[position].priority = new_priority;
if (new_priority < old_priority)
fix_upwards(position);
else
fix_downwards(position); }
And that is just about all that could possibly be said about the mechanics of heap
operations.