Editing Binomial heap (section)

== Structure of a binomial heap ==
A binomial heap is implemented as a set of binomial trees that satisfy the ''binomial heap properties'':<ref name="clrs" />
* Each binomial tree in a heap obeys the ''[[minimum-heap property]]'': the key of a node is greater than or equal to the key of its parent.
* There can be at most one binomial tree for each order, including zero order.
The first property ensures that the root of each binomial tree contains the smallest key in the tree. It follows that the smallest key in the entire heap is one of the roots.<ref name="clrs" />

The second property implies that a binomial heap with <math>n</math> nodes consists of at most <math>1+\log_2 n</math> binomial trees, where <math>\log_2</math> is the [[binary logarithm]]. The number and orders of these trees are uniquely determined by the number of nodes <math>n</math>: there is one binomial tree for each nonzero bit in the [[binary numeral system|binary]] representation of the number <math>n</math>. For example, the decimal number 13 is 1101 in binary, <math>2^3 + 2^2 + 2^0</math>, and thus a binomial heap with 13 nodes will consist of three binomial trees of orders 3, 2, and 0 (see figure below).<ref name="clrs" /><ref name="brown" />
[[File:Binomial-heap-13.svg|alt=Example of a binomial heap|center|325px|Example of a binomial heap containing 13 nodes with distinct keys. The heap consists of three binomial trees with orders 0, 2, and 3.|thumb]]

The number of different ways that <math>n</math> items with distinct keys can be arranged into a binomial heap equals the largest odd divisor of <math>n!</math>. For <math>n=1,2,3,\dots</math> these numbers are
:1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... {{OEIS|A049606}}
If the <math>n</math> items are inserted into a binomial heap in a uniformly random order, each of these arrangements is equally likely.<ref name="brown" />