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 
These lecture slides are adapted 
from CLRS, Chapters 6, 19. 
Page 2


Princeton University  •  COS 423  •  Theory of Algorithms  •  Spring 2002  •  Kevin Wayne  
Binary and Binomial Heaps 
These lecture slides are adapted 
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 
These lecture slides are adapted 
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 
These lecture slides are adapted 
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 
Linked List 
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 
These lecture slides are adapted 
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 
Linked List 
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 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Content Category

Related Searches

practice quizzes

,

Previous Year Questions with Solutions

,

Viva Questions

,

MCQs

,

video lectures

,

ppt

,

Extra Questions

,

past year papers

,

Semester Notes

,

Sample Paper

,

study material

,

Important questions

,

Free

,

Summary

,

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

,

shortcuts and tricks

,

Objective type Questions

,

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

,

mock tests for examination

,

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

,

Exam

,

pdf

;