In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap), as it supports merging two heaps in logarithmic time. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps. Binomial heaps were invented in 1978 by Jean Vuillemin.

A binomial heap is implemented as a set 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 ${\displaystyle k}$ has ${\displaystyle 2^{k}}$ nodes, and height ${\displaystyle k}$. The name comes from the shape: a binomial tree of order ${\displaystyle k}$ has ${\displaystyle {\tbinom {k}{d}}}$ nodes at depth ${\displaystyle d}$, a binomial coefficient. Because of its structure, a binomial tree of order ${\displaystyle k}$ can be constructed from two trees of order ${\displaystyle k-1}$ 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.

A binomial heap is implemented as a set of binomial trees that satisfy the binomial heap properties:

The first property ensures that the root of each binomial tree contains the smallest key in the tree. It follows that the smallest key in the entire heap is one of the roots.

The second property implies that a binomial heap with ${\displaystyle n}$ nodes consists of at most ${\displaystyle 1+\log _{2}n}$ binomial trees, where ${\displaystyle \log _{2}}$ is the binary logarithm. The number and orders of these trees are uniquely determined by the number of nodes ${\displaystyle n}$: there is one binomial tree for each nonzero bit in the binary representation of the number ${\displaystyle n}$. For example, the decimal number 13 is 1101 in binary, ${\displaystyle 2^{3}+2^{2}+2^{0}}$, and thus a binomial heap with 13 nodes will consist of three binomial trees of orders 3, 2, and 0 (see figure below).

The number of different ways that ${\displaystyle n}$ items with distinct keys can be arranged into a binomial heap equals the largest odd divisor of ${\displaystyle n!}$. For ${\displaystyle n=1,2,3,\dots }$ these numbers are

If the ${\displaystyle n}$ items are inserted into a binomial heap in a uniformly random order, each of these arrangements is equally likely.