Content deleted Content added
Pit~enwiki (talk | contribs) m +de: |
m link |
||
Line 20:
Notice in this case, it changes the formulas for the child indices to be 2''n''+1 and 2''n''+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|heap property]], so the two children of a parent can be interchanged.
If you regard the array as a screwed-up heap, you can fix it in [[Big O notation|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.
==External links==
| |||