Binomial Heaps: Merge Better

Merge Better¶

The other day, I was introduced to a really cool data structure: the binomial heap. You might be familiar with binary heaps, which use a binary tree to keep items in heap order; but binomial heaps are a little more obscure. As you would expect, they too retain heap order and are often used in implementing priority queues. However, the advantage of a binomial heap is that it supports log(n) merging given two binomial heaps.

This table sums it up nicely:

In short: with a binomial heap, you earn faster merging, but give up the O(1) find-min of a binary heap.

How It Works: Binomial Trees¶

A binomial heap is made up of a list of binomial trees, so we’ll first discuss the latter structure, which I find to be the particularly ingenious component. A binomial tree is a recursive data structure: a tree of degree zero is just a single node and a tree of degree k is two trees of degree k-1, connected.

Thus:

A tree of degree 1 is just two nodes, i.e., two trees of degree 0.
A tree of degree 2 is four nodes, i.e., two trees of degree 1 (or two trees of two trees of degree zero = four nodes).
A tree of degree 3…

Here's a visual representation: