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 4Flattening 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 4Notice in this case, it changes the formulas for the child indices to be 2

If you regard the array as a screwed-up 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.