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 33: | Line 33: | ||
==Analysis== | ==Analysis== | ||
We use the fact that the height of a binary heap with <math>N</math> nodes is <math>h = \lceil \log_2(N+1) \rceil - 1 \approx \log_2 N</math>. | We use the fact that the height of a binary heap with <math>N</math> nodes is <math>h = \lceil \log_2(N+1) \rceil - 1 \approx \log_2 N</math>. | ||
− | |||
− | |||
===Finding the maximum=== | ===Finding the maximum=== | ||
Line 40: | Line 38: | ||
===Insertion=== | ===Insertion=== | ||
− | A bottom-up heapification, in the worst case, uses approximately <math>\log_2 N</math> swaps (if it goes all the way up to the top of the tree), each of which is assumed to take constant time, giving <math>O(\log N)</math>. However, on average, the newly inserted element does not travel very far up the tree. In particular, assuming a uniform distribution of keys, it has a one-half chance of being greater than its parent; it has a one-half chance of being greater than its grandparent given that it is greater than its parent; it has a one-half chance of being greater than its great-grandparent given that it is greater than its parent, and so on, so that the expected number of swaps is <math>\frac{1}{2} + \frac{ | + | A bottom-up heapification, in the worst case, uses approximately <math>\log_2 N</math> swaps (if it goes all the way up to the top of the tree), each of which is assumed to take constant time, giving <math>O(\log N)</math>. However, on average, the newly inserted element does not travel very far up the tree. In particular, assuming a uniform distribution of keys, it has a one-half chance of being greater than its parent; it has a one-half chance of being greater than its grandparent given that it is greater than its parent; it has a one-half chance of being greater than its great-grandparent given that it is greater than its parent, and so on, so that the expected number of swaps is <math>\frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + ...</math>, an arithmetico-geometric series that converges to 2, so that in the average case insertion takes constant time, <math>O(1)</math> (and the expected final depth of the node is <math>h-2</math>. |
− | + | ||
− | + | ||
===Deletion=== | ===Deletion=== |