Training Material

## Heaps

### Manipulating heaps

A heap is a binary tree with two properties:

1. The tree is filled level by level, without any gaps, so it is a complete binary tree where only the bottom most level may be incomplete.
2. The value at each node is less than or equal to that of its parents.

Here is an example of a heap.

```                         ---3---
/         \
14           11
/   \         /   \
16     19     13     15
/  \   /  \
21   20 23   24
```

Suppose we want to insert an element, say 10, into the heap.

Since we must fill the heap level by level, we can only insert it in the first free position on the bottom row.

```                         ---3---
/         \
14            11
/   \          /   \
16     19      13     15
/  \   /  \     /
21   20 23   24 10
```

This violates the heap property, but only between 10 and its parent. We can fix the problem by swapping 10 with its parent.

```                         ---3---
/         \
14            11
/   \          /   \
16     19      10     15
/  \   /  \     /
21   20 23   24 13
```

This transfers the problem one level up, so we swap again and then stop because there are no further heap violations.

```                         ---3---
/         \
14            10
/   \          /   \
16     19      11     15
/  \   /  \     /
21   20 23   24 13
```

The height of such a complete binary tree with n nodes is at most log n, so we have to "bubble up" the new value at most log n times till the heap is restored to a stable state.

Clearly, the minimum value in a heap is found at the root. Thus, assuming we can compute the parent and children of a node efficiently, we can:

• insert a vertex in log n time
• find the minimum in constant time

But, in Dijkstra's algorithm, we also want to delete the minimum vertex so that it is not considered again later on.

If we delete the minimum value 3 from our heap, we create a hole at the root. How do we restore the structure?

```                         --[  ]--
/         \
14            10
/   \          /   \
16     19      11     15
/  \   /  \     /
21   20 23   24 13
```

In the new heap, we have one less element, so eventually the last slot currently used in the bottom row will be vacant. So, one option is to just move this last value to the root.

```                         ---13--
/         \
14            10
/   \          /   \
16     19      11     15
/  \   /  \
21   20 23   24
```

Now, we have a possible violation of heap property at the root. We examine 13 and its two children and swap it with the smaller of its children, to get the following tree.

```                         ---10--
/         \
14            13
/   \          /   \
16     19      11     15
/  \   /  \
21   20 23   24
```

This pushes the heap violation one step down. Again we swap 13 with the smaller of its children, to get

```                         ---10--
/         \
14            10
/   \          /   \
16     19      13     15
/  \   /  \
21   20 23   24
```

Now we stop. Once again, the number of steps we take is proportional to the height of the tree, so delete-min takes time log n.

Suppose we change 19 to 6?

```                         ---13--
/         \
14            10
/   \          /   \
16      6      11     15
/  \   /  \
21   20 23   24
```

The heap property is violated above 6, so we move it up as we do in insert:

```                         ---6---
/         \
13            10
/   \          /   \
16     14      11     15
/  \   /  \
21   20 23   24
```

```                         ---13--
/         \
14            10
/   \          /   \
16     29      11     15
/  \   /  \
21   20 23   24
```

In this case, we push it down, as in delete-min, till we get a heap.

```                         ---13--
/         \
14            10
/   \          /   \
16     23      11     15
/  \   /  \
21   20 29   24
```

So, changing a value and restoring the heap structure can also be done in log n time.

To summarize, assuming we can find the parent/child of a node efficiently and also find the last element of a heap efficiently, we can perform the following operations efficiently:

• find-min : constant time
• insert : log n time
• delete-min : log n time
• update-value : log n time

How do we store a heap so that we can manipulate it easily?

```                         ---13--
/         \
14            10
/   \          /   \
16     23      11     15
/  \   /  \
21   20 29   24
```

We read off the values, level by level, and store them in an array. The heap above would be an array of the form

[ 13 14 10 16 23 11 15 21 21 20 29 24]

Here is a picture of the heap with each value labelled by its position in the array.

```                         --13(1)--
/           \
14(2)           10(3)
/      \          /   \
16(4)    23(5)   11(6)  15(7)
/  \      /   \
(8)21 (9)20  29(10) 24(11)
```

From this, it is immediate that the children of a node at position j are found at positions 2j and 2j+1. Likewise, the parent of a node a position j is at position floor(j/2), where floor(n) is the largest integer less than or equal to n.