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). A binomial tree is defined recursively:
- A binomial tree of order 0 is a single node
- A binomial tree of order k has a root node whose children are roots of binomial trees of orders k−1, k−2, ..., 2, 1, 0 (in this order).
A binomial tree of order k has 2k 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 root of the other one. 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 has nodes at depth . (See Binomial coefficient.)
Read more about this topic: Binomial Heap
Famous quotes containing the word tree:
“That sound, everywhere about us, of the sea—
the tree among its tresses has always heard it,
and the horse dips his black body in the sound
stretching his neck as if towards drinking water ...”
—Denise Levertov (b. 1923)