Editing Binary heap
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision | Your text | ||
Line 45: | Line 45: | ||
===Deletion=== | ===Deletion=== | ||
− | A top-down heapification, in the worst case, uses approximately <math>\log_2 N</math> swaps (if it goes all the way back down to the bottom of the tree), each of which is assumed to take constant time, giving <math>O(\log N)</math> time. In the average case, the analysis is more complicated. Assume, for simplicity, uniform distribution of keys and assume that no two keys are equal. Consider the path from the root to the now vacated original position of the key that now occupies the root. As long as the key stays on this path, it will have to be swapped down further, because we know it is less than its child on the path, but as soon as the key leaves the path, it finds itself among a subtree of keys whose sizes relative to it are unknown and uniformly distributed. The expected final depth will then be <math>h- | + | A top-down heapification, in the worst case, uses approximately <math>\log_2 N</math> swaps (if it goes all the way back down to the bottom of the tree), each of which is assumed to take constant time, giving <math>O(\log N)</math> time. In the average case, the analysis is more complicated. Assume, for simplicity, uniform distribution of keys and assume that no two keys are equal. Consider the path from the root to the now vacated original position of the key that now occupies the root. As long as the key stays on this path, it will have to be swapped down further, because we know it is less than its child on the path, but as soon as the key leaves the path, it finds itself among a subtree of keys whose sizes relative to it are unknown and uniformly distributed. The expected final depth will then be <math>h-2</math>, as in the insertion analysis. So we find that the overall expected final depth is <math>\frac{1}{2}(h-2) + \frac{1}{4}(h-2) + \frac{1}{8}(h-2) + ... = h-2</math> (where the first term corresponds to the key leaving the path on the first swap, the second the second swap, and so on). Thus, on average, <math>h-2</math> swaps occur, so the average-case time for deletion is no better asymptotically than the worst-case time. |
===Increasing a key=== | ===Increasing a key=== |