Content deleted Content added
fixed diagrams |
enclosed ASCII art in <pre> </pre> to avoid it being disturbed by my bot. |
||
Line 5:
"Greater than" means according to whatever comparison function is chosen to sort the heap, not necessarily "greater than" in the mathematical sense (since the quantities are not even always numerical). Heaps where the comparison function is mathematical "greater than" are called max-heaps; those where the comparison function is mathematical "less than" are called "min-heaps". Conventionally, max-heaps are used, since they are readily applicable for use in [[priority queue]]s.
<pre>
1 11
/ \ / \
Line 13:
/ \ / \ / \ / \
8 9 10 11 1 2 3 4
</pre>
Note that the ordering of siblings in a heap is not specified by the heap property, so the two children of a parent can be freely interchanged.
Line 21:
Say we have a max-heap
<pre>
11
/ \
Line 27:
/ \ /
3 4 X
</pre>
and we want to add the number 15 to the heap. We first place the 15 in the position marked by the X. However the heap property is violated since 15 is greater than 8, so we need to swap the 15 and the 8. So, we have the heap looking as follows after the first swap:
<pre>
11
/ \
Line 35:
/ \ /
3 4 8
</pre>
However the heap property is still violated since 15 is greater than 11, so we need to swap again:
<pre>
15
/ \
Line 43:
/ \ /
3 4 8
</pre>
which is a valid max-heap.
=== Deleting the root from the heap ===
The procedure for deleting the root from the heap - effectively giving the maximum element in a max-heap or the minimum element in a min-heap - is similar to up-heap. What we do is remove the root, then replace it with the last element on the last level. So, if we have the same max-heap as before,
<pre>
11
/ \
Line 54:
/ \
3 4
</pre>
we remove the 11 and replace it with the 4.
<pre>
4
/ \
5 8
/
3
</pre>
Now the heap property is violated since 8 is greater than 4. If we swap these two elements, we have restored the heap property and we need not swap elements further:
<pre>
8
/ \
5 4
/
3
</pre>
== Heap implementation ==
It is perfectly possible to use a traditional binary tree data structure to implement a binary heap. There is an issue with finding the adjacent element on the last level on the binary heap when adding an element which can be resolved algorithmically or by adding extra data to the nodes, called "threading" the tree — that is, instead of merely storing references to the children, we store the [[inorder]] successor of the node as well.
| |||