Binomial heaps
Data Structures and Algorithms
1
DSaA 2012/2013
Mergeable heap
A mergeable heap supports the following five operations:
" MAKE-HEAP() creates and returns a new heap containing no elements.
" INSERT(H, x) inserts node x, whose key field has already been filled in, into
heap H.
" MINIMUM(H) returns a pointer to the node in heap H whose key is
minimum.
" EXTRACT-MIN(H) deletes the node from heap H whose key is minimum,
returning a pointer to the node.
" UNION(H1, H2) creates and returns a new heap that contains all the nodes
of heaps H1 and H2. Heaps H1 and H2 are "destroyed" by this operation.
In addition, the data structure also supports the following two operations:
" DECREASE-KEY(H, x, k) assigns to node x within heap H the new key
value k, which is assumed to be no greater than its current key value.
" DELETE(H, x) deletes node x from heap H.
2
DSaA 2012/2013
Running time comparison
Procedure Binary heap Binomial heap Fibonacci heap
(worst case) (worst case) (amortized)
MAKE-HEAP Q�(1) Q�(1) Q�(1)
INSERT Q�(lg n) O(lg n) Q�(1)
MINIMUM Q�(1) O(lg n) Q�(1)
EXTRACT-MIN Q�(lg n) Q�(lg n) O(lg n)
UNION Q�(n) O(lg n) Q�(1)
DECREASE-KEY Q�(lg n) Q�(lg n) Q�(1)
DELETE Q�(lg n) Q�(lg n) O(lg n)
3
DSaA 2012/2013
Binominial tree
The binomial tree Bk is an ordered defined recursively:
" The binomial tree B0 consists of a single node.
" The binomial tree Bk consists of two binomial trees Bk-1 that are
linked together: the root of one is the leftmost child of the root
of the other
B0
&
Bk-1
B0
Bk-1
B1
B2
Bk-2
Bk-1
Bk
Bk
4
DSaA 2012/2013
The binomial trees
" examples
depth
0
1
2
B0
B1
3
B2
B3
4
B4
5
DSaA 2012/2013
Properties of binomial trees
For the binomial tree Bk:
1. There are 2k nodes
2. The height of the tree is k
k
ć� ��
�� ��
�� ��
3. There are exactly nodes at depth i for i=0,& ,k
i
Ł� ł�
4. The root has degree k, which is greater than
that of any other node; moreover if i the
children of the root are numbered from left to
right by k - 1, k - 2, ..., 0, child i is the root of a
subtree Bi
Corollary:
The maximum degree of any node in an n-node
binomial tree is lg n.
6
DSaA 2012/2013
Binomial heaps
A binomial heap H is a set of binomial trees that
satisfies the following binomial-heap properties:
1. Each binomial tree in H obeys the min-heap
property: the key of a node is greater than or
equal to the key of its parent. We say that each
such tree is min-heap-ordered
2. For any nonnegative integer k, there is at most
one binomial tree in H whose root has degree k
The first property tells us that the root of a min-heap-ordered tree contains the smallest
key in the tree.
The second property implies that an n-node binomial heap H consists of at most lg n + 1
binomial trees. Let the binary representation of n has lg n + 1 bits, ,
Binomial tree Bi appears in H if and only if bit bi= 1. Thus, binomial heap H contains at
most lg n + 1 binomial trees.
7
DSaA 2012/2013
Binomial heaps
" Example, representation
Head[H] 10 1 6
12 25 8 14 29
18 11 17 38
27
10 1 6
0 2 3
Head[H]
p
key
12 25 8 14 29
degree
1 0 2 1 0
child
sibling
18 11 17 38
0 1 0 0
27
0
8
DSaA 2012/2013
Operation on binomial heaps
" Creating a new binomial heap:
Allocate and return an object H, where head[H]=NIL. The
running time is Q�(1).
" Findind the minimum key
The procedure BINOMIAL-HEAP-MINIMUM returns a
pointer to the node with the minimum key in an n-node
binomial heap H. This implementation assumes that
there are no keys with value Ą�.
Binomial-Heap-Minimum(H)
{ 1} y:=NIL
{ 2} x:=head[H]
{ 3} min:= Ą�
{ 4} while x `" NIL do
{ 5} if key[x] < min then
{ 6} min:=key[x]
{ 7} y:=x
{ 8} x:=sibling[x]
{ 9} return y
Running time is Q�(lg n)
9
DSaA 2012/2013
Uniting two binomial heaps
" The operation of uniting two binomial heaps is used as a
subroutine by most of the remaining operations. The
BINOMIAL-HEAP-UNION procedure repeatedly links
binomial trees whose roots have the same degree.
" The following procedure links the Bk-1 tree rooted at node
y to the Bk-1 tree rooted at node z; that is, it makes z the
parent of y. Node z thus becomes the root of a Bk tree.
z
Binomial-Link(y,z)
z y
y
{ 1} p[y]:=z
Bk-1
{ 2} sibling[y]:=child[z]
Bk-1
{ 3} child[z]:=y
Bk-1 Bk-1
{ 4} degree[z]:=degree[z]+1
Bk
Running time is Q�(1)
10
DSaA 2012/2013
Uniting two binomial heaps
" An auxiliary procedure BINOMIAL-HEAP-MERGE is
used that merges the root lists of H1 and H2 into a single
linked list that is sorted by degree into monotonically
increasing order. The BINOMIAL-HEAP-MERGE
procedure, is similar to the MERGE procedure for linked
lists.
" There are 4 cases depending on degrees in x, next_x
and sibling[next_x]
&
prev_x next_x
x
prev_x next_x sibling[next_x]
x
a b c d
a b c d
&
& &
Bk Bl
Case 1
Bk Bl
11
DSaA 2012/2013
Uniting two binomial heaps
prev_x next_x
x
prev_x next_x sibling[next_x]
x
a b c d
a b c d
&
& &
&
Case 2
Bk Bk Bk
Bk Bk Bk
next_x
prev_x x
prev_x next_x sibling[next_x]
x
a b d
a b c d
&
& &
&
c
Case 3
Bk Bl
Bk Bk Bl
key[x] d" key[next_x]
Bk
next_x
prev_x x
prev_x next_x sibling[next_x]
x
a c d
a b c d
&
& &
&
b
Case 4
Bk Bl
Bk Bk Bl
key[x] > key[next_x]
Bk
12
DSaA 2012/2013
Uniting & - example
head[H1]
head[H2]
12 7 15
18 3 6
25 28 33
37 8 29 10 44
41
30 23 22 48 31 17
45 32 24 50
Binomial-Heap-Merge
55
x next_x
head[H]
12 18 7 3 15 6
25 37 28 33 8 29 10 44
41 30 23 22 48 31 17
45 32 24 50
Case 3
55
13
DSaA 2012/2013
Uniting& - example
x next_x
12 7 3 15 6
head[H]
18 25 37 28 33 8 29 10 44
41 30 23 22 48 31 17
45 32 24 50
Case 2
55
x next_x
12 7 3 15 6
head[H]
18 25 37 28 33 8 29 10 44
41 30 23 22 48 31 17
45 32 24 50
Case 4
55
14
DSaA 2012/2013
Uniting & - example
x next_x
12 3 15 6
head[H]
18 7 37 28 33 8 29 10 44
25 41 30 23 22 48 31 17
45 32 24 50
Case 3
55
x next_x
12 3 6
head[H]
18 15 7 37 8 29 10 44
28 33 25 30 23 22 48 31 17
41 45 32 24 50
Case 1
55
15
DSaA 2012/2013
Uniting & - code
Binomial-Heap-Union(H1, H2)
{ 1} H := Make-Binomial-Heap()
{ 2} head[H]:=Binomial-Heap-Merge(H1, H2)
{ 3} free the objects H1 and H2 but not the lists they point to
{ 4} if head[H]=NIL then
{ 5} return H
{ 6} prev_x:=NIL
{ 7} x:=head[H]
{ 8} next_x:=sibling[x]
{ 9} while next_x `" NIL do
{10} if (degree[x]`"degree[next_x]) or (sibling[next_x]`"NIL and
degree[sibling[next_x]]=degree[x]) then
{11} prev_x=x // case 1 and 2
{12} x=next_x // case 1 and 2
{13} else
{14} if key[x]<=key[next_x] then
{15} sibling[x]:=sibling[next_x] // case 3
{16} Binomial-Link(next_x,x) // case 3
{17} else
{18} if prev_x=NIL then // case 4
{19} head[H]:=next_x // case 4
{20} else // case 4
{21} sibling[prev_x]:=next_x // case 4
{22} Binomial-Link(x,next_x) // case 4
{23} x:=next_x // case 4
{24} next_x:=sibling[x]
{25}
return H
Running time is Q�(lg n)
16
DSaA 2012/2013
Inserting a node - code
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 )
Running time is Q�(lg n)
Extracting the node with minimum key
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
Running time is Q�(lg n)
17
DSaA 2012/2013
Extract-Min - example
12 3 6
head[H]
18 15 7 37 8 29 10 44
28 33 25 30 23 22 48 31 17
41 45 32 24 50
55
head[H] 12 6
head[H ] 37 7 15
18 8 29 10 44
25 28 33
30 23 22 48 31 17
41
45 32 24 50
55
Uniting
18
DSaA 2012/2013
Decreasing a key
Binomial-Heap-Decrease-Key(H,x,k)
{ 1} if k > key[x] then
{ 2} error  new key is greater than current key
{ 3} key[x]:=k
{ 4} y:=x
{ 5} z:=p[y]
{ 6} while z`"NIL and key[y]{ 7} exchange key[y] and key[z]
{ 8} if y and z have satellite fields, exchange them, too
{ 9} y:=z
{10} z:=p[y]
Running time is Q�(lg n)
Deleting a key
Binomial-Heap-Delete(H,x)
{ 1} Binomial-Heap-Decrease-Key(H,x,-Ą�)
{ 2} Binomial-Heap-Extract-Min(H)
Running time is Q�(lg n)
19
DSaA 2012/2013
Decreasing a key - example
head[H] 6
8 29 10 44
head[H] 6
k=7
30 23 22 48 31 17
8 29 10 44
x
45 32 24 50
z
30 23 22 48 31 17
55
y
7 32 24 50
55
head[H] 6
z
z
8 29 10 44
head[H] 6
y
7 23 22 48 31 17 y
7 29 10 44
30 32 24 50
8 23 22 48 31 17
55
30 32 24 50
55
20
DSaA 2012/2013