1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
A i(heap) is a kind of i(binary tree) which can be represented by an array. In
the standard heap, the key of an element is not smaller than the key of its
children. This kind of heap is called a em(max heap). A tree in which
numbers are keys could be organized as shown in figure ref(heaptree).
figure(stl/heap)
(A binary tree representation of a heap)
(heaptree)
Such a tree may also be organized in an array:
verb( 12, 11, 10, 8, 9, 7, 6, 1, 2, 4, 3, 5)
In the following description, keep two pointers into this array in mind:
a pointer tt(node) indicates the location of the next node of the tree, a
pointer tt(child) points to the next element which is a child of the tt(node)
pointer. Initially, tt(node) points to the first element, and tt(child) points
to the second element.
itemization(
itt(*node++ (== 12)). 12 is the top node. its children are tt(*child++)
(11) and tt(*child++) (10), both less than 12.
it() The next node (tt(*node++ (== 11))), in turn, has tt(*child++) (8)
and tt(*child++) (9) as its children.
it() The next node (tt(*node++ (== 10))) has tt(*child++) (7)
and tt(*child++) (6) as its children.
it() The next node (tt(*node++ (== 8))) has tt(*child++) (1)
and tt(*child++) (2) as its children.
it() Then, node (tt(*node++ (== 9))) has children tt(*child++) (4)
and tt(*child++) (3).
it() Finally (as far as children are concerned) (tt(*node++ (== 7))) has
one child tt(*child++) (5)
)
Since tt(child) now points beyond the array, the remaining nodes have no
children. So, nodes 6, 1, 2, 4, 3 and 5 don't have children.
Note that the left and right branches are not ordered: 8 is less than 9, but 7
is larger than 6.
A heap is created by traversing a binary tree level-wise, starting from the
top node. The top node is 12, at the zeroth level. At the first level we find
11 and 10. At the second level 8, 9, 7 and 6 are found, etc.
Heaps can be constructed in containers supporting random access. So, a list is
not an appropriate data structure for a heap. Heaps can be constructed from an
(unsorted) array (using link(tt(make_heap))(MAKEHEAP)). The top-element can
be pruned from a heap, followed by reordering the heap (using
link(tt(pop_heap))(POPHEAP)), a new element can be added to the heap,
followed by reordering the heap (using link(tt(push_heap))(PUSHHEAP)), and
the elements in a heap can be sorted (using link(tt(sort_heap))(SORTHEAP),
which, of course, invalidates the heap).
|
