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 19: | Line 19: | ||
Since a binomial heap is only allowed to contain at most one power-of-two tree of each size, the structure of a binomial heap is uniquely determined by the binary representation of its size. For example, if a binomial heap contains 13 elements, that is, {{Binary|1101}}, then we see that <math>13 = 2^0 + 2^2 + 2^3 = 1 + 4 + 8</math>, so a binomial heap of size 13 contains three power-of-two trees, of sizes 1, 4, and 8, respectively. | Since a binomial heap is only allowed to contain at most one power-of-two tree of each size, the structure of a binomial heap is uniquely determined by the binary representation of its size. For example, if a binomial heap contains 13 elements, that is, {{Binary|1101}}, then we see that <math>13 = 2^0 + 2^2 + 2^3 = 1 + 4 + 8</math>, so a binomial heap of size 13 contains three power-of-two trees, of sizes 1, 4, and 8, respectively. | ||
− | It follows that the number of power-of-two trees in a binomial heap is no more than <math>\lceil\ | + | It follows that the number of power-of-two trees in a binomial heap is no more than <math>\lceil\log(n+1)\rceil</math>, since that is the length of the number <math>n</math> expressed as a bit string. |
==Finding the maximum== | ==Finding the maximum== |