Why we can't create a binomial heap in max-heap format instead of min-heap format?


Why do you say that we cannot create a binomial max-heap? Given any min-heap implementation you can always create its max version (and vice-versa).

An easy "black-box" way to see that this is true is considering what happens when all operations involving a key $k$ are actually performed on the key $-k$ instead.

That is, instead of inserting $k$ we insert $-k$; instead of deleting $k$ we delete $-k$; when we need to return the minimum key $k$, we return $-k$; etc...

  • $\begingroup$ "Each binomial tree in a heap obeys the minimum-heap propert." Source: en.wikipedia.org/wiki/Binomial_heap geeksforgeeks.org/binomial-heap-2 $\endgroup$ – Gregory Barlow Dec 30 '20 at 17:11
  • $\begingroup$ That's because the description is trying to build a binomial min-heap. There is nothing that prevents you from building a binomial max-heap. All these constructions are comparison based, as long as you have a total linear order between the keys you can use them. For example you can use the order relation induced by "less than" or that induced by "greater than" (which gives you a min-heap). Another trick is the one I described in my answer. $\endgroup$ – Steven Dec 30 '20 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.