Courses

# Binary and Binomial Heaps Computer Science Engineering (CSE) Notes | EduRev

Created by: Yashu Sharma

## Computer Science Engineering (CSE) : Binary and Binomial Heaps Computer Science Engineering (CSE) Notes | EduRev

``` Page 1

Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2002  •  Kevin Wayne
Binary and Binomial Heaps
from CLRS, Chapters 6, 19.
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.
? . . .
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) ? 8
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
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) ? 8
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 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) ? 8
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
```
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;