Date: Wed, 11 Dec 1996 22:33:49 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Fri, 08 Nov 1996 21:54:14 GMT Content-length: 7570
1 3 5 6 8 9 11 becomes 6 / \ 3 9 / \ / \ 1 5 8 11
Where the middle of the search starts with 6. Then if we need to search the left part of the list, the new middle is 3; if we need to search the right part, though, the middle is 9, and so on down the tree. This is one way that an array can represent a tree.
However, there is another type of tree with an array can represent, called a heap. There are two things required in order for a tree to be a heap:
o o o o o o o / / \ / \ / \ / \ / \ o o o o o o o o o o o / / \ / \ / / \ / \ o o o o o o o o o o
8 / \ 4 2
is a heap, whereas
4 / \ 2 8
is not.
How are heaps represented by arrays? Elements of a heap are read left-to-right, top-to-bottom. So
8 / \ 6 4 / \ / \ 3 5 2 1 is stored as 8 6 4 3 5 2 1 (I'll be referring to this array as LIST from now on)
2 / \ 6 4 / \ / \ 3 5 8 1 2 6 4 3 5 8 1 Suppose we wanted to Heapify node 1 (LIST(1)=2).
2 < 6, so clearly the heap propert is violated. Also, 2 < 4. So we want to move the node down in the tree. So we switch 6 and 2:
6 / \ 2 4 / \ / \ 3 5 8 1 6 2 4 3 5 8 1We chose 6 because 6 > 4 (if we chose 4, 4 would be at the top with 6 as one of its children, so the heap property would still fail at node 1.
We continue to follow the 2, now located at LIST(2). The heap property still fails there, so we need to switch the 2 and the 5. We get
6 / \ 5 4 / \ / \ 3 2 8 1 6 5 4 3 2 8 1
Note that this is still not a heap (the 8 is a problem), but all nodes on the path from where the 2 was to where the 2 is now satisfy the heap property.
What we're essentially going to do is call heapify within a DO loop. We won't need to call Heapify on the bottom nodes (usually called Leaf nodes); Those nodes have no children, so they're as far down as they can go.
2 / \ 4 6 / \ / \ 1 7 3 8 ----------------------------- Heapify Node 3 (the 6) 2 / \ 4 8 / \ / \ 1 7 3 6 6 < 8, so we had to Heapify, and we chose 8 because 8 8 > 3. So / \ is a heap. 3 6 ----------------------------- Heapify Node 2 (the 4) 2 / \ 7 8 / \ / \ 1 4 3 6 7 So / \ is a heap. 1 4 ----------------------------- Heapify Node 1 (the 2) This ecompasses 2 moves...2 gets switched with the 8, then with the 6). 8 / \ 7 6 / \ / \ 1 4 3 2 -----------------------------
Why start with N/2 and work backwards? Suppose we're given Heaps H1,H2 and a and a node X; the tree
X / \ H1 H2
can only violate the heap property at one place...X. So if we switch X with the top of H1, then X is fine, H2 is fine, but H1 may not be fine. So, let's look at H1.....
X H1 now = / \ H3 H4 (H3 and H4 are subheaps)
We're back to the same argument we just had above...If X violates the heap property, move in down into H3 or H4. This is exactly what Heapify does.
So the only node to violate the heap property will always be X. Once heapify finds the right spot for X, then even X isn't a problem, so all nodes are fine, and we have our heap.
This is why we work back from N/2 to 1. We build heaps out of the lower parts of the tree, then use them to build a heap out of higher parts of the tree. In our example, we made a heap out of the tree starting with LIST(3), then a heap out of the tree starting at LIST(2). We then used those two subheaps to build a heap out of the tree starting with LIST(1).
8 / \ 4 7 / \ / \ 3 1 2 5 8 4 7 3 1 2 5
7 / \ 4 5 / \ / 3 1 2 7 4 5 3 1 2 8
so the next time thru, for example, switch 2 and 7, decrease your heap size by 1, and Heapify the top. 5 / \ 4 2 / \ 3 1 5 4 2 3 1 7 8
So now the 2 largest elements are in order, at the back of the list. So when you're done, you'll have the entire list is sorted order.