We describe a heap data structure that supports Minimum, Insert, and
Borrow at O(1) worst-case cost, Delete at O(lg n)
worst-case cost including at most lg n + O(1) element
comparisons, and Union at O(lg n) worst-case cost including at
most lg n + O(lg lg n) element comparisons, where n
denotes the (total) number of elements stored in the data structure(s)
prior to the operation. As the resulting data structure consists of
two components that are different variants of binomial heaps, we call
it a bipartite binomial heap. Compared to its counterpart, a
multipartite binomial heap, the new structure is simpler and
mergeable, still retaining the efficiency of the other operations.

@article{EJK2017J,
author = {Amr Elmasry and Claus Jensen and Jyrki Katajainen},
title = {Bipartite binomial heaps},
journaltitle = {RAIRO---Theoretical Informatics and Applications},
volume = {51},
number = {3},
year = {2017},
pages = {121--133},
}