Binomial Heaps

Difficulty: *

My impression is that this is the easiest of the tests so far.  The majority of students completed Parts I and II and so picked up most of the marks.  The average mark was around 78%.  The final question is rather unsatisfactory for a number of reasons; I was aware of this at time, but had no time to fix it and am not sure even now how to make it more interesting!  It did, however, succeed in spreading the marks.


Template File

More Information

Chapter 19 of the MIT Algorithms Book provides a comprehensive coverage of Binomial Heaps.  Chris Osaki’s PhD thesis, Purely Functional Data Structures, includes a chapter on binomial heaps that is similar to what you see here.  Another implementation can be found in the Haskell library Data.Heap.Binomial by Brendan Hickey.