CSE 548: Analysis of Algorithms

Lecture 9
( Binomial Heaps )

Rezaul A. Chowdhury
Department of Computer Science
SUNY Stony Brook
Fall 2017
 Mergeable Heap Operations
MAKE-HEAP( ): return a new heap containing only element
INSERT( , ): insert element into heap
MINIMUM( ): return a pointer to an element in containing
the smallest key
EXTRACT-MIN( ): delete an element with the smallest key from
and return a pointer to that element
UNION( , ): return a new heap containing all elements of
heaps and , and destroy the input heaps
More mergeable heap operations:
DECREASE-KEY( , , ): change the key of element of heap to
assuming the current key of
DELETE( , ): delete element from heap
 Mergeable Heap Operations

Heap Binary Heap Binomial Heap

Operation ( worst-case ) ( amortized )

MAKE-HEAP Θ 1 Θ 1

INSERT Ο log Θ 1

MINIMUM Θ 1 Θ 1

EXTRACT-MIN Ο log Ο log

UNION Θ Θ 1

DECREASE-KEY Ο log

DELETE Ο log
 Binomial Trees
A binomial tree is an ordered tree defined recursively as follows.
consists of a single node
0,
−

− For consists of two ’s that are linked together

so that the root of one is the left child of the root of the other
 Binomial Trees
Some useful properties of are as follows.
1. it has exactly 2 nodes
2. its height is

3. there are exactly nodes

at depth 0,1,2, … ,
4. the root has degree
5. if the children of the root
are numbered from left to
right by 1, 2, … , 0,
then child is the root of a
 Binomial Trees
Prove: has exactly nodes at depth 0,1,2, … , .

Proof: Suppose has , nodes at depth .

0 # $ 0 %& ,
, !1 # 0,
, , %'()&* ).

, ,

, 1 , , ,

, , ,

, ,
 Binomial Trees
0 # $ 0 %& ,
, !1 # 0,
, , %'()&* ).

⇒ , / 0 0 01 , , 0

Generating function: , - , , - , - … , -

, 2 - 3 , - 3 , - 3 , - / 01 3 / 01-
4 4 4 4

3 , - -3 , - 0
4 4

, - -, - 0 1 - , - / 01

1 # 0,
⇒, - 5
1 - , - %'()&* ).

1 -
Equating the coefficient of - from both sides: ,
 Binomial Heaps
A binomial heap is a set of binomial trees that satisfies the
following properties:
 Binomial Heaps
A binomial heap is a set of binomial trees that satisfies the
following properties:
1. each node has a key
2. each binomial tree in obeys the min-heap property
3. for any integer 0 0, there is at most one binomial tree
in whose root node has degree

6 1 10

min
8 14 29 12 25

11 17 38 18

27
 Rank of Binomial Trees
The rank of a binomial tree node , denoted &9 , is the
number of children of .

3
The figure on the right shows the rank
of each node in .
2 1 0
Observe that &9 &%%'
1 0 0
.

Rank of a binomial tree is the rank of 0

its root. Hence,
&9 &9 &%%'
 A Basic Operation: Linking Two Binomial Trees
Given two binomial trees of the same rank, say, two ’s, we link
them in constant time by making
;
the root of one tree the left child
of the root of the other, and thus 6

producing a ; . 8 14 29

If the trees are part of a binomial 11 17 38

min-heap, we always make the root 27

with the smaller key the parent,

and the one with the larger key
the child.

Ties are broken arbitrarily.

Binomial Heap Operations: UNION( , )

8 12

min
11 17

27
<

6 1 18

min
14 29 25

38

min <
Binomial Heap Operations: UNION( , )

8 12

min
11 17

27
<

6 1 18

min
14 29 25

38

12

min
18
Binomial Heap Operations: UNION( , )

8 12

min
11 17

27

6 1 18

min
14 29 25

<
38

12

min
18
Binomial Heap Operations: UNION( , )

8 12

min
11 17

27

6 1 18

min
14 29 25

<
38

1 12

12 25 18

18

min
Binomial Heap Operations: UNION( , )

8 12

min
11 17

27
<

6 1 18

min
14 29 25

38

12 25

18

min
Binomial Heap Operations: UNION( , )

8 12

min
11 17

27
<

6 1 18

min
14 29 25

38

6 1

8 14 29 12 25

11 17 38 18

27 min
Binomial Heap Operations: UNION( , )

8 12

min
11 17

27

6 1 18

min
14 29 25

38

=>?@> ,
6 1

8 14 29 12 25

11 17 38 18

27 min
 Binomial Heap Operations: UNION( , )
UNION , works in exactly the same way as binary addition.

Let be the number of nodes in A 1,2B.

Then the largest binomial tree in

is a C
, where log .

Thus can be treated as a 1

bit binary number , where bit D is 1
if contains a E, and 0 otherwise.

If F % , , then can
be viewed as a log bit
binary number ,
where .
 Binomial Heap Operations: UNION( , )
UNION , works in exactly the same way as binary addition.

Initially, does not contain any binomial trees.

Melding starts from ( LSB ) and

continues up to ( MSB ).

At each location D ∈ /0, 1, one

encounters at most three ( 3 ) E ’s:

− at most 1 from ( input ),

at most 1 from ( input ), and
if D 0, at most 1 from ( carry )
−
−
 Binomial Heap Operations: UNION( , )
UNION , works in exactly the same way as binary addition.
When the number of E ’s at location D ∈ /0, 1 is:
0: location D of is set to <
1: location D of
−
− points to that E
− 2: the two E ’s are linked to produce
a E; which is stored as a carry
at location D 1 of , and
location D is set to <
− 3: two E ’s are linked to produce
a E; which is stored as a
carry at location D 1 of
, and the 3rd E is
stored at location D
 Binomial Heap Operations: UNION( , )
UNION , works in exactly the same way as binary addition.

Worst case cost of UNION , is clearly Θ log , where is

the total number of nodes in and .

Observe that this operation fills out

1 locations of , where log .

It does only Θ 1 work for each

location.

Hence, total cost is Θ Θ log .

 Binomial Heap Operations: UNION( , )
One can improve the performance of UNION , as follows.
W.l.o.g., suppose is at least as large as , i.e., 0 .
We also assume that has enough
space to store at least up to , where,
log .
Then instead of melding and
to a new heap , we can meld them
in-place at .
After melding till H , we stop once
the carry stops propagating.
The cost is Ω , but Ο .
Worst-case cost is still Ο Ο log .
 Binomial Heap Operations: INSERT( , )
Step 1: ′ ← MAKE-HEAP ′

Takes Θ 1 time.
5

min ′

Step 2: ← UNION , ′
8 12

( in-place at )
Takes Ο log time, where
min
11 17

27

is the number of nodes in .

Thus the worst-case cost of

INSERT , is Ο log , where
8 5

min
11 17 12

27

is the number of items already

in the heap.
 Binomial Heap Operations: EXTRACT-MIN( )
6

Step 1:
min
Step 2: remove the binomial tree with
remove the smallest root from the input heap
6 10
minimum
element 8 14 29 12 25

11 17 38 18

27
10

min <
12 25

Step 3: remove the root of the binomial 18

tree with the minimum element, and form
a new binomial heap from the children of

,
the removed root
K
Step 4: UNION and update the min pointer

′
8 14 29
8 14 29

min ′ <
11 17 38
10 11 17 38

min
27
12 25 27

18
 Binomial Heap Operations: EXTRACT-MIN( )
6

Step 1:
min
Step 2: remove the binomial tree with
remove the smallest root from the input heap

Θ 1
6 10
minimum
element
Θ 1
8 14 29 12 25

11 17 38 18

27
10

min <
12 25

Step 3: remove the root of the binomial 18

Tree with the minimum element, and form
a new binomial heap from the children of

,
the removed root
Ο log
K
Step 4: UNION and update the min pointer
Ο log
′
8 14 29
8 14 29

min ′ <
11 17 38
10 11 17 38

min
27
12 25 27

18
Thus, the worst-case cost of
EXTRACT-MIN is Ο log
 Binomial Heap Operations

Heap
Worst-case
Operation

MAKE-HEAP Θ 1

INSERT Ο log

MINIMUM Θ 1

EXTRACT-MIN Ο log

UNION Ο log
 Amortized Analysis ( Accounting Method )
We maintain a credit account for every tree in the heap, and
always maintain the following invariant:

L M&)N ' E 1
OP ∈Q

MAKE-HEAP( ):
actual cost, M 1 ( for creating the singleton heap )
extra charge, R 1 ( for storing in the credit account
of the new tree )
amortized cost, M̂ M R 2 Θ 1
 Amortized Analysis ( Accounting Method )
We maintain a credit account for every tree in the heap, and
always maintain the following invariant:

L M&)N ' E 1
OP ∈Q

LINK( T ,T
A B A B
):
actual cost, M 1 ( for linking the two trees )
We use M&)N '
A B
pay for this actual work.
Let ; be the newly created tree. We restore the credit invariant
by transferring M&)N ' to M&)N '
A B
; .
Hence, amortized cost, M̂ M R 1 1 0
 Amortized Analysis ( Accounting Method )
We maintain a credit account for every tree in the heap, and
always maintain the following invariant:

L M&)N ' E 1
OP ∈Q

INSERT( , ):
Amortized cost of MAKE-HEAP is 2
Then UNION , K is simply a sequence of free LINK operations
with only a constant amount of additional work that do not create
any new trees. Thus the credit invariant is maintained, and the
amortized cost of this step is 1.
Hence, amortized cost of INSERT, M̂ 2 1 3 Θ 1
 Amortized Analysis ( Accounting Method )
We maintain a credit account for every tree in the heap, and
always maintain the following invariant:

L M&)N ' E 1
OP ∈Q

UNION( , ):
UNION , includes a sequence of free LINK operations that
maintain the credit invariant.
But it also includes Ο log other operations that are not free
( e.g., consider melding a heap with 2 elements with one
containing 1 elements ). These operations do not create new
trees (and so do not violate the credit invariant), and each cost Θ 1 .
Hence, amortized cost of UNION, M̂ Ο log
 Amortized Analysis ( Accounting Method )
We maintain a credit account for every tree in the heap, and
always maintain the following invariant:

L M&)N ' E 1
OP ∈Q

EXTRACT-MIN( ):
Steps 1 & 2: The Θ 1 actual cost is paid for by the credit released
by the deleted tree.
Step 3: Exposes Ο log new trees, and we charge 1 unit of extra
credit for storing in the credit account of each such tree.
Step 4: Performs a UNION that has Ο log amortized cost.
Hence, amortized cost of EXTRACT-MIN, M̂ Ο log
 Amortized Analysis ( Potential Method )
Potential Function,
Φ V M W ( #trees in the data structure after the -th operation ),
where M is a constant.
Clearly, Φ V 0 ( no trees in the data structure initially )
and for all 0, Φ V 0 0 ( #trees cannot be negative )

MAKE-HEAP( ):
actual cost, M 1 ( for creating the singleton heap )
potential change, Δ Φ V Φ V M
( as #trees increases by 1 )
amortized cost, M̂ M Δ 1 M Θ 1
 Amortized Analysis ( Potential Method )
Potential Function,
Φ V M W ( #trees in the data structure after the -th operation ),
where M is a constant.
INSERT( , ):
The number of trees increases by 1 initially.
Then the operation scans 0 ( say ) locations of the array
of tree pointers. Observe that we use tree linking A 1B times each
of which reduces the number of trees by 1.
actual cost, M 1
potential change, Δ Φ V Φ V MA1 1 B
M M 1
amortized cost, M̂ M Δ 2 M AM 1BA 1B
For M 0 1, we have, M̂ 2 M Θ 1
 Amortized Analysis ( Potential Method )
Potential Function,
Φ V M W ( #trees in the data structure after the -th operation ),
where M is a constant.
UNION( , ):
Suppose the operation scans 0 locations of the array of
tree pointers, and uses the link operation < times. Observe that
< 0 0. Each link reduces the number of trees by 1.
actual cost, M
potential change, Δ Φ V Φ V MW<
amortized cost, M̂ M Δ MW<

Since Ο log and < Ο log , we have,

M̂ Ο log for any M.
 Amortized Analysis ( Potential Method )
Potential Function,
Φ V M W ( #trees in the data structure after the -th operation ),
where M is a constant.
EXTRACT-MIN( ):
Let in Step 1: & rank of the tree with the smallest key
and in Step 4: #locations of pointer array scanned during UNION
< #link operations during UNION
' #trees in the heap after the UNION

Then actual cost, M 1 step 1 1 step 2 & step 3

step 4: union ' A step 4: update b ptr B
2 ' &
 Amortized Analysis ( Potential Method )
Potential Function,
Φ V M W ( #trees in the data structure after the -th operation ),
where M is a constant.
EXTRACT-MIN( ):
Let in Step 1: & rank of the tree with the smallest key
and in Step 4: #locations of pointer array scanned during UNION
< #link operations during UNION
' #trees in the heap after the UNION

potential change, Δ Φ V Φ V
M W & 1 A removing b element in step 1
removes 1 tree but creates & new ones B
MW< A linkings in step 4
reduces #trees by < B
 Amortized Analysis ( Potential Method )
Potential Function,
Φ V M W ( #trees in the data structure after the -th operation ),
where M is a constant.
EXTRACT-MIN( ):
Let in Step 1: & rank of the tree with the smallest key
and in Step 4: #locations of pointer array scanned during UNION
< #link operations during UNION
' #trees in the heap after the UNION
actual cost, M 2 ' &
potential change, Δ Φ V Φ V MW & < 1
Then amortized cost, M̂ M Δ 2 ' & MW & < 1
Since Ο log , < Ο log , ' Ο log && Ο log ,
we have, M̂ Ο log for any M.
 Binomial Heap Operations

Heap
Worst-case Amortized
Operation

MAKE-HEAP Θ 1 Θ 1

INSERT Ο log Θ 1

MINIMUM Θ 1 Θ 1

EXTRACT-MIN Ο log Ο log

UNION Ο log Ο log

 Binomial Heaps with Lazy Union
We maintain pointers to the trees in a doubly linked circular list
( instead of an array ), but do not maintain a b pointer.
 Binomial Heap Operations with Lazy Union
We maintain the following invariant: L M&)N ' E 2
OP ∈Q

MAKE-HEAP( ): Create a singleton heap as before. Hence,

amortized cost Θ 1 .
LINK( T ,T
A B A B
): The two input trees have 4 units of saved credits
of which 1 unit will be used to pay for the actual cost of linking, and
2 units will be saved as credit for the newly created tree. So, linking
is still free, and it has 1 unused credit that can be used to pay for
additional work if necessary.
UNION( , ): Simply concatenate the two root lists into one,
and update the min pointer. Clearly, amortized cost Θ 1 .
INSERT( , ): This is MAKE-HEAP followed by a UNION. Hence,
amortized cost Θ 1 .
 Binomial Heap Operations with Lazy Union
We maintain the following invariant: L M&)N ' E 2
OP ∈Q

EXTRACT-MIN( ): Unlike in the array version, in this case we may

have several trees of the same rank.
We create an array of length log 1 with each location
containing a < pointer. We use this array to transform the linked list
version to array version.
We go through the list of trees of , inserting them one by one into
the array, and linking and carrying if necessary so that finally we
have at most one tree of each rank. We also create a min pointer.
We now perform EXTRACT-MIN as in the array case.
Finally, we collect the nonempty trees from the array into a doubly
linked list, and return.
 Binomial Heap Operations with Lazy Union
We maintain the following invariant: L M&)N ' E 2
OP ∈Q

EXTRACT-MIN( ): We only need to show that converting from linked

list version to array version takes Ο log amortized time.
Suppose we start with ' trees, and perform < links. So, we spend
Ο ' < time overall.
As each link decreases the number of trees by 1, after < links we end
up with ' < trees. Since at that point we have at most one tree of
each rank, we have ' < log 1.
Thus ' < 2< ' < Ο < log .
The Ο < part can be paid for by the < extra credits from < links.
We only charge the Ο log part to EXTRACT-MIN.
 Binomial Heap Operations with Lazy Union
We use exactly the same potential function as in the previous version,
Φ V M W ( #trees in the data structure after the -th operation ),
where M is a constant.
As before, clearly, Φ V 0
and for all 0, Φ V 0 0
MAKE-HEAP( ):
actual cost, M 1 ( for creating the singleton heap )
potential change, Δ Φ V Φ V M
( as #trees increases by 1 )
amortized cost, M̂ M Δ 1 M Θ 1
 Binomial Heap Operations with Lazy Union
We use exactly the same potential function as in the previous version,
Φ V M W ( #trees in the data structure after the -th operation ),
where M is a constant.
UNION( , ):
actual cost, M 1 ( for merging the two doubly linked lists )
potential change, Δ Φ V Φ V 0
( no new tree is created or destroyed )
amortized cost, M̂ M Δ 1 Θ 1
 Binomial Heap Operations with Lazy Union
We use exactly the same potential function as in the previous version,
Φ V M W ( #trees in the data structure after the -th operation ),
where M is a constant.

INSERT( , ):
Constant amount of work is done by MAKE-HEAP and UNION,
and MAKE-HEAP creates a new tree.

actual cost, M 1 1 2
potential change, Δ Φ V Φ V M

amortized cost, M̂ M Δ 2 M Θ 1
 Binomial Heap Operations with Lazy Union
We use exactly the same potential function as in the previous version,
Φ V M W ( #trees in the data structure after the -th operation ),
where M is a constant.
EXTRACT-MIN( ):
Cost of creating the array of pointers is log 1.
Suppose we start with ' trees in the doubly linked list, and perform <
link operations during the conversion from linked list to array version.
So we perform ' < work, and end up with ' < trees.
Cost of converting to the linked list version is ' <.

actual cost, M log 1 ' < ' < 2' log 1

potential change, Δ Φ V Φ V MW<
 Binomial Heap Operations with Lazy Union
We use exactly the same potential function as in the previous version,
Φ V M W ( #trees in the data structure after the -th operation ),
where M is a constant.
EXTRACT-MIN( ):
actual cost, M log 1 ' < ' < 2' log 1
potential change, Δ Φ V Φ V MW<

amortized cost, M̂ M Δ 2 ' < log 1 M 2 W<

But ' < log 1 ( as we have at most one tree of each rank )

So, M̂ 3 log 3 M 2 W<

3 log 3 ( assuming M 0 2 )
Ο log
 Binomial Heap Operations

Heap Amortized Amortized

Worst-case
Operation ( Eager Union ) ( Lazy Union )

Θ 1 Θ 1 Θ 1
MAKE-
HEAP
INSERT Ο log Θ 1 Θ 1

MINIMUM Θ 1 Θ 1 Θ 1

Ο log Ο log Ο log

EXTRACT-
MIN
UNION Ο log Ο log Θ 1