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:
“It is, I fear, but a vain show of fulfilling the heathen precept, “Know thyself,” and too often leads to a self-estimate which will subsist in the absence of that fruit by which alone the quality of the tree is made evident.”
—George Eliot [Mary Ann (or Marian)