The diagram on the left is somewhat deceptive in that heaps are conventionally in decreasing order rather than increasing order because of their use as priority queues. The diagram on the right is a more traditional heap.
1 11 / \ / \ / \ / \ 2 3 9 10 / \ / \ / \ / \ 4 5 6 7 5 6 7 8 / \ / \ / \ / \ 8 9 10 11 1 2 3 4
Flattening these two heaps into a traditional zero based array will produce the following arrays:
index: 0 1 2 3 4 5 6 7 8 9 10 left: 1 2 3 4 5 6 7 8 9 10 11 right: 11 9 10 5 6 7 8 1 2 3 4
Notice in this case, it changes the formulas for the child indices to be 2n+1 and 2n+2. The fact that a heap can easily be flattened is the basis for the heapsort algorithm. Also note that the ordering of siblings in a heap is not specified by the heap property, so the two children of a parent can be interchanged.
If you regard the array as a screwedup heap, you can fix it in O(n) time by restoring the heap property from the bottom up. Consider each trio containing a node and its two children, starting from the end of the array; if the greatest value of the three nodes is not in the top node, exchange it with the top node. This puts the former top node at the top of a subtree which may contain nodes greater than it is; so we must compare it with its new children and possibly repeat the process.
Search Encyclopedia

Featured Article
