Content deleted Content added
Tag: Reverted |
|||
Line 99:
In the worst case, the new root has to be swapped with its child on each level until it reaches the bottom level of the heap, meaning that the delete operation has a time complexity relative to the height of the tree, or O(log ''n'').
A simple alternative is to extract root to leaf, recursively. Save the root element to return, and select the right or left side for a replacement based on the max of right and left keys and if equal selecting the left if on insert either left was favored on equal balance or for stable sort, right was favored on an equal key to the root. Extract from the selected side and place that element into the root. If using height or similar balance, adjust height or balance after returning from the child extract, before returning the saved former root, possibly to a parent node call.
=== Insert then extract ===
| |||