CmSc 250 Fundamentals of Computing III

Binary Heaps

The IdeaA binary heap is a complete binary tree, where

each node has a higher priority than its children.

This is calledheap-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.

Binary heap implementation with an arraySince the tree is complete, we use the following array implementation:

Given array

A:

A(1)- contains the root

The node inA(i)has its left child inA(2*i), its right child inA(2*i+1),

and its parent inA([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 position in the array is 5.

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).Basic operations3. 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 thanO(logN)percolations up.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 isO(logN).

Other heap operations

4. 1. DecreaseKey(p,d)This operation lowers the value of the element at position

pby a positive amountd. 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 bypercolating up.

4. 2. IncreaseKey(p,d)This operation increases the value of the element at position

pby a positive amountd. 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 bypercolating down.4. 3. Remove(p)

With this operation an element

pis removed from the queue. This is done in two steps:

- Assigning the highest priority to
p - percolate p up to the root.- Deleting the element in the root and filling the hole by percolating down the last element in the queue.
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

Nelements 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.The idea:

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 130A[1] is the root, A[1] = 150. Its children are A[2] and A[3], the children of A[2] are A[4] and A[5], 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.

- 110 is less that its children - OK
- 70 is not less than its children . 50 is the node to go up one level.
- 10 is OK
- 30 is not less than its children, 20 is the node to go up
After processing the nodes at height 1 we have the following tree:

Next we examine the nodes at height 2:

- 40 is OK
- 80 needs to be percolated down twice.
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.

Complexity:

The worst case for a node at height

kiskpercolations.

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 heighthcontainingN = 2nodes,^{h+1}- 1

the sumSof the heights of the nodes isS = 2^{h+1}- 1 - (h + 1) = O(N)

Proof:We can see that the tree has 1 node at height

h, 2 nodes at heighth - 1, 4 nodes at heighth - 2, etc. Thus we have:nodes height

1 (2^{0}) h2 (2

^{1}) h - 14 (2

^{2}) h - 28 (2

^{3}) h - 3…….

2

^{h}0Hence we have

S = S 2

^{i}(h - i), i = 0 to hS = 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)

**
Learning Goals**

- Know what a binary heap is and how it is implemented by an array.
- Given a list of integer elements be able to build the binary heap on paper and show how the elements are located in an arrray
- Know the basic operations for a binary heap, be able to perform deletion and insertion on paper.

**
Exam-like questions**

- What is the "structure property" of a binary heap?
- What is the "order property" of a binary heap?
- How can a binary heap be implemented by an array?
- Given a list of elements with priorities: 21, 13,17,10,7,11 do
the following:
- Build the binary heap (draw the tree at each step) and show the corresponding array
- Delete the element with the highest priority, drawing the tree at each step of the deleting procedure
- Insert a new element with priority 15 and draw the tree at each step of the insertion procedure

- What is the complexity of deletion in binary heaps in the worst case? Explain your answer
- What is the complexity of insertion in binary heaps in the worst case? Explain your answer.

Back to Contents page

Created by Lydia Sinapova