Courses

Binary and Binomial Heaps Notes | EduRev

: Binary and Binomial Heaps Notes | EduRev

``` Page 1

Princeton University  â€¢  COS 423  â€¢  Theory of Algorithms  â€¢  Spring 2002  â€¢  Kevin Wayne
Binary and Binomial Heaps
from CLRS, Chapters 6, 19.
2
Priority Queues
Supports the following operations.
¦ Insert element x.
¦ Return min element.
¦ Return and delete minimum element.
¦ Decrease key of element x to k.
Applications.
¦ Dijkstraâ€™s shortest path algorithm.
¦ Primâ€™s MST algorithm.
¦ Event-driven simulation.
¦ Huffman encoding.
¦ Heapsort.
¦ . . .
3
Priority Queues in Action
PQinit()
for each v ? V
key(v) â€¹¥
PQinsert(v)
key(s) â€¹ 0
while (!PQisempty())
v = PQdelmin()
for each w ? Q s.t (v,w) ? E
if p (w) > p (v) + c(v,w)
PQdecrease(w, p (v) + c(v,w))
Dijkstraâ€™s Shortest Path Algorithm
4
Dijkstra/Prim
1 make-heap
|V| insert
|V| delete-min
|E| decrease-key
Priority Queues
make-heap
Operation
insert
find-min
delete-min
union
decrease-key
delete
1
Binary
log N
1
log N
N
log N
log N
1
Binomial
log N
log N
log N
log N
log N
log N
1
Fibonacci *
1
1
log N
1
1
log N
1
Relaxed
1
1
log N
1
1
log N
1
1
N
N
1
1
N
is-empty 1 1 1 1 1
Heaps
O(|E| + |V| log |V|) O(|E| log |V|) O(|V|
2
)
Page 2

Princeton University  â€¢  COS 423  â€¢  Theory of Algorithms  â€¢  Spring 2002  â€¢  Kevin Wayne
Binary and Binomial Heaps
from CLRS, Chapters 6, 19.
2
Priority Queues
Supports the following operations.
¦ Insert element x.
¦ Return min element.
¦ Return and delete minimum element.
¦ Decrease key of element x to k.
Applications.
¦ Dijkstraâ€™s shortest path algorithm.
¦ Primâ€™s MST algorithm.
¦ Event-driven simulation.
¦ Huffman encoding.
¦ Heapsort.
¦ . . .
3
Priority Queues in Action
PQinit()
for each v ? V
key(v) â€¹¥
PQinsert(v)
key(s) â€¹ 0
while (!PQisempty())
v = PQdelmin()
for each w ? Q s.t (v,w) ? E
if p (w) > p (v) + c(v,w)
PQdecrease(w, p (v) + c(v,w))
Dijkstraâ€™s Shortest Path Algorithm
4
Dijkstra/Prim
1 make-heap
|V| insert
|V| delete-min
|E| decrease-key
Priority Queues
make-heap
Operation
insert
find-min
delete-min
union
decrease-key
delete
1
Binary
log N
1
log N
N
log N
log N
1
Binomial
log N
log N
log N
log N
log N
log N
1
Fibonacci *
1
1
log N
1
1
log N
1
Relaxed
1
1
log N
1
1
log N
1
1
N
N
1
1
N
is-empty 1 1 1 1 1
Heaps
O(|E| + |V| log |V|) O(|E| log |V|) O(|V|
2
)
5
Binary Heap:  Definition
Binary heap.
¦ Almost complete binary tree.
â€“ filled on all levels, except last, where filled from left to right
¦ Min-heap ordered.
â€“ every child greater than (or equal to) parent
06
14
78
18
81 77 91
45
53 47
64 84 99 83
6
Binary Heap:  Properties
Properties.
¦ Min element is in root.
¦ Heap with N elements has height = º log
2
Nß .
06
14
78
18
81 77 91
45
53 47
64 84 99 83
N = 14
Height = 3
7
Binary Heaps:  Array Implementation
Implementing binary heaps.
¦ Use an array:  no need for explicit parent or child pointers.
â€“Parent(i) = º i/2ß â€“Left(i)   = 2i
â€“Right(i)  = 2i + 1
06
14
78
18
81 77 91
45
53 47
64 84 99 83
1
2
3
4
56
7
89 10 11 12 13 14
8
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
06
14
78
18
81 77 91
45
53 47
64 84 99 83 42
next free slot
Page 3

Princeton University  â€¢  COS 423  â€¢  Theory of Algorithms  â€¢  Spring 2002  â€¢  Kevin Wayne
Binary and Binomial Heaps
from CLRS, Chapters 6, 19.
2
Priority Queues
Supports the following operations.
¦ Insert element x.
¦ Return min element.
¦ Return and delete minimum element.
¦ Decrease key of element x to k.
Applications.
¦ Dijkstraâ€™s shortest path algorithm.
¦ Primâ€™s MST algorithm.
¦ Event-driven simulation.
¦ Huffman encoding.
¦ Heapsort.
¦ . . .
3
Priority Queues in Action
PQinit()
for each v ? V
key(v) â€¹¥
PQinsert(v)
key(s) â€¹ 0
while (!PQisempty())
v = PQdelmin()
for each w ? Q s.t (v,w) ? E
if p (w) > p (v) + c(v,w)
PQdecrease(w, p (v) + c(v,w))
Dijkstraâ€™s Shortest Path Algorithm
4
Dijkstra/Prim
1 make-heap
|V| insert
|V| delete-min
|E| decrease-key
Priority Queues
make-heap
Operation
insert
find-min
delete-min
union
decrease-key
delete
1
Binary
log N
1
log N
N
log N
log N
1
Binomial
log N
log N
log N
log N
log N
log N
1
Fibonacci *
1
1
log N
1
1
log N
1
Relaxed
1
1
log N
1
1
log N
1
1
N
N
1
1
N
is-empty 1 1 1 1 1
Heaps
O(|E| + |V| log |V|) O(|E| log |V|) O(|V|
2
)
5
Binary Heap:  Definition
Binary heap.
¦ Almost complete binary tree.
â€“ filled on all levels, except last, where filled from left to right
¦ Min-heap ordered.
â€“ every child greater than (or equal to) parent
06
14
78
18
81 77 91
45
53 47
64 84 99 83
6
Binary Heap:  Properties
Properties.
¦ Min element is in root.
¦ Heap with N elements has height = º log
2
Nß .
06
14
78
18
81 77 91
45
53 47
64 84 99 83
N = 14
Height = 3
7
Binary Heaps:  Array Implementation
Implementing binary heaps.
¦ Use an array:  no need for explicit parent or child pointers.
â€“Parent(i) = º i/2ß â€“Left(i)   = 2i
â€“Right(i)  = 2i + 1
06
14
78
18
81 77 91
45
53 47
64 84 99 83
1
2
3
4
56
7
89 10 11 12 13 14
8
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
06
14
78
18
81 77 91
45
53 47
64 84 99 83 42
next free slot
9
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
06
14
78
18
81 77 91
45
53 47
64 84 99 83 42 42
swap with parent
10
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
06
14
78
18
81 77 91
45
42 47
64 84 99 83 42 53
swap with parent
11
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
¦ O(log N) operations.
06
14
78
18
81 77 91
42
45 47
64 84 99 83 53
stop:  heap ordered
12
Binary Heap:  Decrease Key
Decrease key of element x to k.
¦ Bubble up until itâ€™s heap ordered.
¦ O(log N) operations.
06
14
78
18
81 77 91
42
45 47
64 84 99 83 53
Page 4

Princeton University  â€¢  COS 423  â€¢  Theory of Algorithms  â€¢  Spring 2002  â€¢  Kevin Wayne
Binary and Binomial Heaps
from CLRS, Chapters 6, 19.
2
Priority Queues
Supports the following operations.
¦ Insert element x.
¦ Return min element.
¦ Return and delete minimum element.
¦ Decrease key of element x to k.
Applications.
¦ Dijkstraâ€™s shortest path algorithm.
¦ Primâ€™s MST algorithm.
¦ Event-driven simulation.
¦ Huffman encoding.
¦ Heapsort.
¦ . . .
3
Priority Queues in Action
PQinit()
for each v ? V
key(v) â€¹¥
PQinsert(v)
key(s) â€¹ 0
while (!PQisempty())
v = PQdelmin()
for each w ? Q s.t (v,w) ? E
if p (w) > p (v) + c(v,w)
PQdecrease(w, p (v) + c(v,w))
Dijkstraâ€™s Shortest Path Algorithm
4
Dijkstra/Prim
1 make-heap
|V| insert
|V| delete-min
|E| decrease-key
Priority Queues
make-heap
Operation
insert
find-min
delete-min
union
decrease-key
delete
1
Binary
log N
1
log N
N
log N
log N
1
Binomial
log N
log N
log N
log N
log N
log N
1
Fibonacci *
1
1
log N
1
1
log N
1
Relaxed
1
1
log N
1
1
log N
1
1
N
N
1
1
N
is-empty 1 1 1 1 1
Heaps
O(|E| + |V| log |V|) O(|E| log |V|) O(|V|
2
)
5
Binary Heap:  Definition
Binary heap.
¦ Almost complete binary tree.
â€“ filled on all levels, except last, where filled from left to right
¦ Min-heap ordered.
â€“ every child greater than (or equal to) parent
06
14
78
18
81 77 91
45
53 47
64 84 99 83
6
Binary Heap:  Properties
Properties.
¦ Min element is in root.
¦ Heap with N elements has height = º log
2
Nß .
06
14
78
18
81 77 91
45
53 47
64 84 99 83
N = 14
Height = 3
7
Binary Heaps:  Array Implementation
Implementing binary heaps.
¦ Use an array:  no need for explicit parent or child pointers.
â€“Parent(i) = º i/2ß â€“Left(i)   = 2i
â€“Right(i)  = 2i + 1
06
14
78
18
81 77 91
45
53 47
64 84 99 83
1
2
3
4
56
7
89 10 11 12 13 14
8
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
06
14
78
18
81 77 91
45
53 47
64 84 99 83 42
next free slot
9
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
06
14
78
18
81 77 91
45
53 47
64 84 99 83 42 42
swap with parent
10
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
06
14
78
18
81 77 91
45
42 47
64 84 99 83 42 53
swap with parent
11
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
¦ O(log N) operations.
06
14
78
18
81 77 91
42
45 47
64 84 99 83 53
stop:  heap ordered
12
Binary Heap:  Decrease Key
Decrease key of element x to k.
¦ Bubble up until itâ€™s heap ordered.
¦ O(log N) operations.
06
14
78
18
81 77 91
42
45 47
64 84 99 83 53
13
Binary Heap:  Delete Min
Delete minimum element from heap.
¦ Exchange root with rightmost leaf.
¦ Bubble root down until itâ€™s heap ordered.
â€“ power struggle principle:  better subordinate is promoted
06
14
78
18
81 77 91
42
45 47
64 84 99 83 53
14
Binary Heap:  Delete Min
Delete minimum element from heap.
¦ Exchange root with rightmost leaf.
¦ Bubble root down until itâ€™s heap ordered.
â€“ power struggle principle:  better subordinate is promoted
53
14
78
18
81 77 91
42
45 47
64 84 99 83 06
15
Binary Heap:  Delete Min
Delete minimum element from heap.
¦ Exchange root with rightmost leaf.
¦ Bubble root down until itâ€™s heap ordered.
â€“ power struggle principle:  better subordinate is promoted
53
14
78
18
81 77 91
42
45 47
64 84 99 83
exchange with left child
16
Binary Heap:  Delete Min
Delete minimum element from heap.
¦ Exchange root with rightmost leaf.
¦ Bubble root down until itâ€™s heap ordered.
â€“ power struggle principle:  better subordinate is promoted
14
53
78
18
81 77 91
42
45 47
64 84 99 83
exchange with right child
Page 5

Princeton University  â€¢  COS 423  â€¢  Theory of Algorithms  â€¢  Spring 2002  â€¢  Kevin Wayne
Binary and Binomial Heaps
from CLRS, Chapters 6, 19.
2
Priority Queues
Supports the following operations.
¦ Insert element x.
¦ Return min element.
¦ Return and delete minimum element.
¦ Decrease key of element x to k.
Applications.
¦ Dijkstraâ€™s shortest path algorithm.
¦ Primâ€™s MST algorithm.
¦ Event-driven simulation.
¦ Huffman encoding.
¦ Heapsort.
¦ . . .
3
Priority Queues in Action
PQinit()
for each v ? V
key(v) â€¹¥
PQinsert(v)
key(s) â€¹ 0
while (!PQisempty())
v = PQdelmin()
for each w ? Q s.t (v,w) ? E
if p (w) > p (v) + c(v,w)
PQdecrease(w, p (v) + c(v,w))
Dijkstraâ€™s Shortest Path Algorithm
4
Dijkstra/Prim
1 make-heap
|V| insert
|V| delete-min
|E| decrease-key
Priority Queues
make-heap
Operation
insert
find-min
delete-min
union
decrease-key
delete
1
Binary
log N
1
log N
N
log N
log N
1
Binomial
log N
log N
log N
log N
log N
log N
1
Fibonacci *
1
1
log N
1
1
log N
1
Relaxed
1
1
log N
1
1
log N
1
1
N
N
1
1
N
is-empty 1 1 1 1 1
Heaps
O(|E| + |V| log |V|) O(|E| log |V|) O(|V|
2
)
5
Binary Heap:  Definition
Binary heap.
¦ Almost complete binary tree.
â€“ filled on all levels, except last, where filled from left to right
¦ Min-heap ordered.
â€“ every child greater than (or equal to) parent
06
14
78
18
81 77 91
45
53 47
64 84 99 83
6
Binary Heap:  Properties
Properties.
¦ Min element is in root.
¦ Heap with N elements has height = º log
2
Nß .
06
14
78
18
81 77 91
45
53 47
64 84 99 83
N = 14
Height = 3
7
Binary Heaps:  Array Implementation
Implementing binary heaps.
¦ Use an array:  no need for explicit parent or child pointers.
â€“Parent(i) = º i/2ß â€“Left(i)   = 2i
â€“Right(i)  = 2i + 1
06
14
78
18
81 77 91
45
53 47
64 84 99 83
1
2
3
4
56
7
89 10 11 12 13 14
8
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
06
14
78
18
81 77 91
45
53 47
64 84 99 83 42
next free slot
9
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
06
14
78
18
81 77 91
45
53 47
64 84 99 83 42 42
swap with parent
10
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
06
14
78
18
81 77 91
45
42 47
64 84 99 83 42 53
swap with parent
11
Binary Heap:  Insertion
Insert element x into heap.
¦ Insert into next available slot.
¦ Bubble up until itâ€™s heap ordered.
â€“ Peter principle:  nodes rise to level of incompetence
¦ O(log N) operations.
06
14
78
18
81 77 91
42
45 47
64 84 99 83 53
stop:  heap ordered
12
Binary Heap:  Decrease Key
Decrease key of element x to k.
¦ Bubble up until itâ€™s heap ordered.
¦ O(log N) operations.
06
14
78
18
81 77 91
42
45 47
64 84 99 83 53
13
Binary Heap:  Delete Min
Delete minimum element from heap.
¦ Exchange root with rightmost leaf.
¦ Bubble root down until itâ€™s heap ordered.
â€“ power struggle principle:  better subordinate is promoted
06
14
78
18
81 77 91
42
45 47
64 84 99 83 53
14
Binary Heap:  Delete Min
Delete minimum element from heap.
¦ Exchange root with rightmost leaf.
¦ Bubble root down until itâ€™s heap ordered.
â€“ power struggle principle:  better subordinate is promoted
53
14
78
18
81 77 91
42
45 47
64 84 99 83 06
15
Binary Heap:  Delete Min
Delete minimum element from heap.
¦ Exchange root with rightmost leaf.
¦ Bubble root down until itâ€™s heap ordered.
â€“ power struggle principle:  better subordinate is promoted
53
14
78
18
81 77 91
42
45 47
64 84 99 83
exchange with left child
16
Binary Heap:  Delete Min
Delete minimum element from heap.
¦ Exchange root with rightmost leaf.
¦ Bubble root down until itâ€™s heap ordered.
â€“ power struggle principle:  better subordinate is promoted
14
53
78
18
81 77 91
42
45 47
64 84 99 83
exchange with right child
17
Binary Heap:  Delete Min
Delete minimum element from heap.
¦ Exchange root with rightmost leaf.
¦ Bubble root down until itâ€™s heap ordered.
â€“ power struggle principle:  better subordinate is promoted
¦ O(log N) operations.
14
18
78
53
81 77 91
42
45 47
64 84 99 83
stop:  heap ordered
18
Binary Heap:  Heapsort
Heapsort.
¦ Insert N items into binary heap.
¦ Perform N delete-min operations.
¦ O(N log N) sort.
¦ No extra storage.
19
H
1
H
2
14
78
18
81 77 91
11
62 53
64 84 99 41
Binary Heap:  Union
Union.
¦ Combine two binary heaps H
1
and H
2
into a single heap.
¦ No easy solution.
â€“ W (N) operations apparently required
¦ Can support fast union with fancier heaps.
20
Priority Queues
make-heap
Operation
insert
find-min
delete-min
union
decrease-key
delete
1
Binary
log N
1
log N
N
log N
log N
1
Binomial
log N
log N
log N
log N
log N
log N
1
Fibonacci *
1
1
log N
1
1
log N
1
Relaxed
1
1
log N
1
1
log N
1