Binomial heap

In computer science, a binomial heap is a heap similar to a binary heap but also supports quick merging of two heaps. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap abstract data type (also called meldable heap), which is a priority queue supporting merge operation.

A binomial heap is implemented as a collection of binomial trees (compare with a binary heap, which has a shape of a single binary tree), which are defined recursively as follows:

A binomial tree of order k has 2^k nodes, height k.

Because of its unique structure, a binomial tree of order k can be constructed from two trees of order k−1 trivially by attaching one of them as the leftmost child of the root of the other tree. This feature is central to the merge operation of a binomial heap, which is its major advantage over other conventional heaps.

The name comes from the shape: a binomial tree of order ${\displaystyle n}$ has ${\displaystyle {\tbinom {n}{d}}}$ nodes at depth ${\displaystyle d}$. (See Binomial coefficient.)

...
Wikipedia