A binomial queue is a priority queue that is implemented not as a single tree
but as a collection of heap-ordered trees.
A collection of trees is called a *forest* .
Each of the trees in a binomial queue has a very special shape
called a binomial tree.
Binomial trees are general trees.
I.e., the maximum degree of a node is not fixed.

The remarkable characteristic of binomial queues is that the merge operation is similar in structure to binary addition. I.e., the collection of binomial trees that make up the binomial queue is like the set of bits that make up the binary representation of a non-negative integer. Furthermore, the merging of two binomial queues is done by adding the binomial trees that make up that queue in the same way that the bits are combined when adding two binary numbers.

- Binomial Trees
- Binomial Queues
- Implementation
- Merging Binomial Queues
- Putting Items into a Binomial Queue
- Removing an Item from a Binomial Queue

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.