- Each binomial tree within a binomial heap is stored in the left child, right-sibling representation.
- Each node has a key field and any other satellite information required by the application. In addition, each node x contains pointers p[x] to its parent, child[x] to its leftmost child, and sibling[x] to the sibling of x immediately to its right.
- If node x is a root, then p[x] = NIL. If node x has no children, then child[x] = NIL
- If x is the rightmost child of its parent, then sibling[x] = NIL. Each node x also contains the field degree[x], which is the number of children of x.
- The roots of the binomial trees within a binomial heap are organized in a linked list, which we refer to as the root list.
- The degrees of the roots strictly increase as we traverse the root list.
- By the second binomial-heap property, in an n-node binomial heap the degrees of the roots are a subset of {0, 1, ..., ⌊lg n⌋}.
- The sibling field has a different meaning for roots than for non-roots.
- If x is a root, then sibling[x] points to the next root in the root list. (As usual, sibling[x] = NIL if x is the last root in the root list).
- A given binomial heap H is accessed by the field head[H], which is simply a pointer to the first root in the root list of H .
- If binomial heap H has no elements, then head[H] = NIL.
