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.
Binomial heap
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:
Structure of a binomial heap
A binomial heap is implemented as a set of binomial trees that satisfy the binomial heap properties:
Find minimum
To find the minimum element of the heap, find the minimum among the roots of the binomial trees. This can be done in <math>O(\log n)</math> time, as there are just <math>O(\log n)</math> tree roots to examine.