A binary heap is a complete binary tree, where each node has a higher
priority than its children.
This is called heap-order property.
Complete binary tree: Each node has two children,
except for the last two levels.
(The nodes at the last level do not have children.)
New nodes are inserted at the last level from left to right.
This is called heap-structure property.
The tree below is a Complete Binary Heap Tree:
Next node to be inserted - right child of the yellow node.
3. 2. Binary heap implementation with an array
Since the tree is complete, we use the following array implementation:
Given array A:
A(1) - contains the root
The node in A(i) has its left child in A(2*i),
its right child in A(2*i+1),
and its parent in A([i/2]).
The smallest element is always at the root, thus the access
time
to the element with highest priority is constant O(1).
|
6 |
10 |
12 |
15 |
17 |
21 |
23 |
20 |
19 |
34 |
|
This is the array that implements the binary heap in the example.
The nodes of the tree are written in the array level by level
from left to right.
The first element in the array
is 6 - this is the node at level 0.
Then come 10 and 12 -
the nodes at level 1.Further we have 15, 17
(children of 10),
then 18 and 23 (children of 12) - all at level 2.
Finally we have 20, 19 and 34 - the nodes at the last level.
Let's take a node in the array and find its parent
and its children.
Consider for example 17.
Its parent 12 is at position [5/2] = 2
Its left child is at position 5*2 = 10, this is the element 34,
and its right child is at position 2*5 + 1 = 11, (still empty).
3. 3. Basic operations
3. 3. 1. Insert a node - percolate up
A hole is created at the bottom of the tree, in the next available position.
If the new node has a greater value than the parent of the hole -
we insert the node in the hole.
Thus, if the new value to be inserted is 18, our new binary
heap would be:
If the new value is less than its parent, we slide down
the parent of the hole, so the hole moves up, and check to see
if the new node is less than the parent of the new hole.
This process is repeated until we find a place for the new node,
possibly at the very root of the binary heap.
Let's say we want to insert 16. 16 is less than 17, so we slide down 17, and the hole appears at the node where 17 used to be:
Since 16 is less than 10, we can insert it in the hole:
Complexity of insertion: O(logN) in the worst case.
To insert a node in the worst case we would need to percolate up to the
root
of the binary heap tree. Since the tree is a complete tree,
the longest path from the bottom to the top is not longer than O(logN),
where N is the number of nodes in the tree.
Hence we would do no more than O(logN) percolations up.
3. 3. 2. Deleting a node - percolate down
We delete the node at the root - this is the node with
highest priority.
After deleting there is a hole at the root,
which has to be filled.
We may think of sliding the "hole" down and moving up the smaller of the children of the "hole", and repeat this until the hole gets to the bottom. The hole may appear anywhere at the bottom, and if it is not at the last node, the tree is not anymore a complete binary tree.
(You may try this approach on the tree below and see what happens with the tree.)
To make sure that the hole appears at the last node, we render the deletion to an insertion in top-down direction. We can try to insert in the hole the last element that has been inserted, i.e. the rightmost element in the lowest row (the last element in the array). Thus in the array the last element will become empty, and the tree will be complete.
The last element in the example is 18. The hole is at the root.
Most certainly, 18 will not fit there, and we have
to percolate the hole down
The left child of the hole is with higher priority than
the right one.
We slide the hole down to the left:
Still, 18 does not fit in the new hole, it has lower priority than its children 15 and 17. The left child of the hole is with higher priority than the right one. We slide the hole down to the left:
Now 18 fits the hole, and we can safely insert it there:
Complexity of deletion: O(logN) in the worst case.
We always delete from the top, hence the time to access the element with highest
priority is a constant. However, after deletion we have to fill in the
hole at the root. In the worst case we will percolate down to the bottom. Since the hight of
the tree is O(logN), where N is the number of nodes, the worst running time
is O(logN).
