Inserting a node
The following procedure inserts node x into binomial heap H , assuming that x has already been allocated and key[x] has already been filled in.
BINOMIAL-HEAP-INSERT(H, x)
1 H′ ← MAKE-BINOMIAL-HEAP()
2 p[x] ← NIL
3 child[x] ← NIL
4 sibling[x] ← NIL
5 degree[x] ← 0
6 head[H′] ← x
7 H ← BINOMIAL-HEAP-UNION(H, H′)
Analysis:-
The procedure simply makes a one-node binomial heap H′ in O(1) time and unites it with the
n-node binomial heap H in O(lg n) time. The call to BINOMIAL-HEAP-UNION takes care of
freeing the temporary binomial heap H′.
