Revision as of 21:24, 9 June 2003 edit Kyokpae~enwiki (talk \| contribs) 39 edits mNo edit summary ← Previous edit		Revision as of 08:00, 22 June 2003 edit undo Notheruser (talk \| contribs) 3,948 edits m fmt links Next edit →
Line 22: If you regard the array as a screwed-up heap, you can fix it in [[Big O\|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:~~links== * http://mathworld.wolfram.com/Heap.html

Binary heap: Difference between revisions