We describe how a textbook version of a binomial heap that supports the operations find-min, insert, meld, and delete at a logarithmic cost can be modified—by successive data-structural transformations—to support find-min, insert, and meld at O(1) worst-case cost and delete at O(lgn) worst-case cost; n is the number of elements in the data structure. These bounds are asymptotically optimal. We also show that the number of element comparisons performed by the respective operations is at most 0, 5, 5, and 2lgn + O(lglgn).

@unpublished{EJK2011bM,
  author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
  title = {Fast meldable heaps via data-structural transformations},
  year = {2011},
  howpublished = {Unpublished typescript},
}