Content deleted Content added
→Heap operations: ce: word choice, “conform to” seemed to allow that the heap was somehow out of conformance prior to the operation; “preserve” is better because it emphasizes that, of the two definitional properties, ‘shape’ is the one that is more fragile/intractable to repair, and that is why it is the one that must be “preserved” first. Tags: Mobile edit Mobile web edit |
m Correct deletion of an arbitrary element in an heap. The element that should be removed actually needs to be removed. |
||
Line 141:
# Find the index <math>i</math> of the element we want to delete
# Swap this element with the last element. Remove the last element after the swap.
# Down-heapify or up-heapify to restore the heap property. In a max-heap (min-heap), up-heapify is only required when the new key of element <math>i</math> is greater (smaller) than the previous one because only the heap-property of the parent element might be violated. Assuming that the heap-property was valid between element <math>i</math> and its children before the element swap, it can't be violated by a now larger (smaller) key value. When the new key is less (greater) than the previous one then only a down-heapify is required because the heap-property might only be violated in the child elements.
| |||