Editing Binomial heap (section)

== Binomial heap ==
A binomial heap is implemented as a set of '''binomial [[tree data structure|trees]]''' (compare with a [[binary heap]], which has a shape of a single [[binary tree]]), which are defined recursively as follows:<ref name="clrs" />
* A binomial tree of order 0 is a single node
* A binomial tree of order <math>k</math> has a root node whose children are roots of binomial trees of orders <math>k-1</math>, <math>k-2</math>, ..., 2, 1, 0 (in this order).

[[File:Binomial Trees.svg|center|thumb|500px|Binomial trees of order 0 to 3: Each tree has a root node with subtrees 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.]]

A binomial tree of order <math>k</math> has <math>2^k</math> nodes, and height <math>k</math>.
The name comes from the shape: a binomial tree of order <math>k</math> has <math>\tbinom k d</math> nodes at depth <math>d</math>, a [[binomial coefficient]].
Because of its structure, a binomial tree of order <math>k</math> can be constructed from two trees of order <math>k-1</math> by attaching one of them as the leftmost child of the root of the other tree. This feature is central to the ''merge'' operation of a binomial heap, which is its major advantage over other conventional heaps.<ref name="clrs" /><ref name=brown>{{cite journal|last=Brown|first=Mark R.|doi=10.1137/0207026|issue=3|journal=SIAM Journal on Computing|mr=483830|pages=298–319|title=Implementation and analysis of binomial queue algorithms|volume=7|year=1978}}</ref>