The current code walks the whole list before doing anything. It turns out this is actually quite easy to fix. The trick is to build a queue with an extra invariant: that the roots of the binomial trees are decreasing. We can write an insertMaxQ function that takes an element at least as large as the largest element in such a queue and produces a queue that again satisfies the extra condition. This actually turns out to be easy to do!
The current code walks the whole list before doing anything. It turns out this is actually quite easy to fix. The trick is to build a queue with an extra invariant: that the roots of the binomial trees are decreasing. We can write an
insertMaxQfunction that takes an element at least as large as the largest element in such a queue and produces a queue that again satisfies the extra condition. This actually turns out to be easy to do!