A binomial heap is a collection of BINOMIAL TREES, so this section starts by defining binomial trees and proving some key properties.Then i'll define binomial heaps and show how they can be represented.
BINOMIAL TREES-
- Represented as Bk , where B is for binomial and K is the degree(number of children of root)
- Binomial Tree Bk is an ordered tree which is recursive in nature. Ordered trees are the trees containing nodes which can be ordered according to specific criteria.The tree is ordered generally when at every node,all the elements in its left child tree are smaller than elements in in its right subtrees.
- It's RECURSIVE in nature.By this it means that higher degree trees can be made or simply consists of lower degree trees.like
which have been highlighted. For example, the order 3 binomial tree is connected to an order 2, 1, and 0
(highlighted as blue, green and red respectively) binomial tree
- Binomial trees of order 0 to 3: Each tree has a root node with sub-trees of all lower ordered binomial trees, which have been highlighted. For example, the order 3 binomial tree is connected to an order 2, 1, and 0 (highlighted as blue, green and red respectively) binomial tree.
- Degree can be known either by children of root node or by height of tree.like in above height is 3.
continuebinomial-trees.php
