A heap is a binary tree with two properties:
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:
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.
What about updating a value?
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
Suppose, instead, we had increased the value at 19 to 29?
---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:
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.
©IARCS 2012–2016
Pěstujeme web | visit: Skluzavky