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 83Read More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!