Extracting the node with minimum key
The following procedure extracts the node with the minimum key from binomial heap H and returns a pointer to the extracted node.
BINOMIAL-HEAP-EXTRACT-MIN(H)
1 find the root x with the minimum key in the root list of H,
and remove x from the root list of H
2 H′ ← MAKE-BINOMIAL-HEAP()
3 reverse the order of the linked list of x's children,
and set head[H′] to point to the head of the resulting list
4 H ← BINOMIAL-HEAP-UNION(H, H′)
5 return x
Analysis:-
Since each of lines 1-4 takes O(lg n) time if H has n nodes, BINOMIAL-HEAP-EXTRACTMIN
runs in O(lg n) time.
This procedure works as shown.The input binomial heap H is shown in Figure(a)
. Figure
(b) shows the situation after line 1: the root x with the minimum key has
been removed from the root list of H . If x is the root of a Bk-tree, then by property 4 of
x's children, from left to right, are roots of Bk-1-, Bk-2-, ..., B0-trees. Figure
(c) shows that by reversing the list of x's children in line 3, we have a binomial heap H'
that contains every node in x's tree except for x itself. Because x's tree was removed from H in
line 1, the binomial heap that results from uniting H and H′ in line 4, shown in Figure(d),
contains all the nodes originally in H except for x. Finally, line 5 returns x.
The action of BINOMIAL-HEAP-EXTRACT-MIN.
(a) A binomial heap H.
(b)
The root x with minimum key is removed from the root list of H .
(c) The linked list of x's
children is reversed, giving another binomial heap H′.
(d) The result of uniting H and H'.
