CmSc 250 Fundamentals of Computing III
- The Idea
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.
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
to the element with highest priority is constant O(1).
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.
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. 2. Deleting a node - percolate down
We delete the node at the root - this is the node with
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).
4. 1. DecreaseKey(p,d)
This operation lowers the value of the element at position p by a positive amount d. It is used to increase the priority of an element. We have to find a new position of the element according to its new priority by percolating up.
4. 2. IncreaseKey(p,d)
This operation increases the value of the element at position p by a positive amount d. It is used to decrease the priority of an element. We have to find a new position of the element according to its new priority by percolating down.
4. 3. Remove(p)
With this operation an element p is removed from the queue. This is done in two steps:
What does it mean to assign the highest priority?
We need to have a sentinel value for the priorities - a value that is less than
all possible values assigned as priorities. For example, if the priorities are positive numbers,
the value 0 will be a sentinel value.
4. 4. BuildHeap
This operation takes as input N elements and places
them into an empty heap
through successive inserts. The worst case running time is bound by O(NlogN).
However, there is another algorithm to build the binary heap, that runs in O(N) time.
Given an array of elements to be inserted in the heap, treat the array as a heap with order property violated, and then do operations to fix the order property.
Let the array A be:
--- 150 80 40 30 10 70 110 100 20 90 60 50 120 140 130
A is the root, A = 150. Its children are A and A, the children of A are A and A, etc. The corresponding tree is:
In order to fix the order property we compare the nodes with their children starting with the rightmost node at the height 1.
After processing the nodes at height 1 we have the following tree:
Next we examine the nodes at height 2:
The new tree will be:
Next we examine the node at height 3 - the root
150 needs to be percolated down three times - until it gets to the bottom
(Double dotted line indicates two percolates)
Now the tree is in order.
The worst case for a node at height k is k percolations.
Thus at worst the number of operation is equal to the sum of the heights of the nodes in the tree.
Theorem: For a perfect binary tree of height h
containing N = 2 h+1
- 1 nodes,
the sum S of the heights of the nodes is S = 2 h+1 - 1 - (h + 1) = O(N)
We can see that the tree has 1 node at height h, 2 nodes at height h - 1, 4 nodes at height h - 2, etc. Thus we have:
nodes height1 (20) h
2 (21) h - 1
4 (22) h - 2
8 (23) h - 3
Hence we have
S= S 2i (h - i), i = 0 to h
S = h + 2(h - 1) + 4(h - 2) + 8 (h - 3) + …. 2(h-2).2 + 2(h-1).1 (1)
Multiply by 2:
2S = 2h + 4(h - 1) + 8(h - 2) + 16 (h - 3) + …. 2(h-1).2 + 2(h).1 (2)
Subtract (1) from (2):
S = h -2h + 2 + 4 + 8 + …. 2 h
= - h - 1 + (2 h+1 - 1)
= (2 h+1 - 1) - (h + 1)
Note: 1 + 2 + 4 + 8 + …. 2 h = (2 h+1 - 1)
Hence S = (2 h+1 - 1) - (h + 1)
Hence the complexity of building a heap with N nodes is linear O(N)