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:
“As a tree my sin stands
To darken all lands;
Death is the fruit it bore.”
—Christina Georgina Rossetti (1830–1894)