Editing Binomial 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 82: | Line 82: | ||
==Deletion== | ==Deletion== | ||
Once we have identified the minimum element in the binomial heap, which takes logarithmic time, we can remove it, as follows. Suppose the minimum element is the root of the power-of-two tree with size <math>2^k</math>. Then, we remove this tree from the heap and split the tree into two trees of size <math>2^{k-1}</math>. Whichever one does not contain the minimum element, we split again, so that now we have a tree of size <math>2^{k-1}</math> and two trees of size <math>2^{k-2}</math>. One of these two new trees again does not contain the minimum element, so we split it again. We continue splitting until finally we end up with one power-of-two tree of size <math>2^{k-1}</math>, one of size <math>2^{k-2}</math>, and so on down; one of size 4, one of size 2, and two of size 1. One of the two singletons will be the minimum element, so we simply destroy that node. The rest of the power-of-two trees constitute an entire binomial heap in and of themselves, which is then merged back into the original heap from which we removed the tree of size <math>2^k</math>. This procedure uses a logarithmic number of splits, which takes logarithmic time, followed by a merge of two binomial heaps, which takes logarithmic time; so it is <math>O(\log n)</math> overall. | Once we have identified the minimum element in the binomial heap, which takes logarithmic time, we can remove it, as follows. Suppose the minimum element is the root of the power-of-two tree with size <math>2^k</math>. Then, we remove this tree from the heap and split the tree into two trees of size <math>2^{k-1}</math>. Whichever one does not contain the minimum element, we split again, so that now we have a tree of size <math>2^{k-1}</math> and two trees of size <math>2^{k-2}</math>. One of these two new trees again does not contain the minimum element, so we split it again. We continue splitting until finally we end up with one power-of-two tree of size <math>2^{k-1}</math>, one of size <math>2^{k-2}</math>, and so on down; one of size 4, one of size 2, and two of size 1. One of the two singletons will be the minimum element, so we simply destroy that node. The rest of the power-of-two trees constitute an entire binomial heap in and of themselves, which is then merged back into the original heap from which we removed the tree of size <math>2^k</math>. This procedure uses a logarithmic number of splits, which takes logarithmic time, followed by a merge of two binomial heaps, which takes logarithmic time; so it is <math>O(\log n)</math> overall. | ||
− | |||
− | |||
==Binomial tree representation== | ==Binomial tree representation== |