Talk:Data Structures/Min and Max Heaps

From Wikibooks, the open-content textbooks collection

The algorithm for removing an extreme element is just wrong, as far as I can see. It "percolates" the hole down the tree, but not necessarily to the last element in the array, which is where it has to be for subsequent truncation of that array to work. The algorithm as it stands will remove whatever is last in the array, regardless of where the hole is. When the hole has not percolated to the last element of the array, an element will be lost, and another will be duplicated.

The correct algorithm is to start by put the last array element at the first position in the array and then percolate that down. This guarantees the last element has been vacated, ready for truncation of the array.