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. 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 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 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. ¦ . . . 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 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 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 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) ‹¥ 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 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 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) ‹¥ 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 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 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) ‹¥ 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 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 Linked List 1 N N 1 1 N is-empty 1 1 1 1 1 HeapsRead More

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