Page 1 1 Priority Queues Sections 6.1 to 6.5 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] R l r ll lr rr rl root Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] ll r l R 6 5 4 3 2 1 0 Page 2 1 Priority Queues Sections 6.1 to 6.5 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] R l r ll lr rr rl root Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] ll r l R 6 5 4 3 2 1 0 2 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] lr ll r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] rl lr ll r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] rr rl lr ll r l R 6 5 4 3 2 1 0 Priority Queue Note: STL provides deleteMax. But book provides deleteMin. We’ll follow the deleteMax strategy. deleteMax Priority Queue Usage int main() { priority_queue<int> Q; Q.push(1); Q.push(4); Q.push(2); Q.push(8); Q.push(5); Q.push(7); assert(Q.size() == 6); assert(Q.top() == 8); Q.pop(); assert(Q.top() == 7); Q.pop(); assert(Q.top() == 5); Q.pop(); assert(Q.top() == 4); Q.pop(); assert(Q.top() == 2); Q.pop(); assert(Q.top() == 1); Q.pop(); assert(Q.empty()); } STL Priority Queues ? Element type with priority ?<typename T> t ?Compare & cmp ? Associative queue operations ?Void push(t) ?void pop() ?T& top() ?void clear() ?bool empty() Page 3 1 Priority Queues Sections 6.1 to 6.5 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] R l r ll lr rr rl root Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] ll r l R 6 5 4 3 2 1 0 2 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] lr ll r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] rl lr ll r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] rr rl lr ll r l R 6 5 4 3 2 1 0 Priority Queue Note: STL provides deleteMax. But book provides deleteMin. We’ll follow the deleteMax strategy. deleteMax Priority Queue Usage int main() { priority_queue<int> Q; Q.push(1); Q.push(4); Q.push(2); Q.push(8); Q.push(5); Q.push(7); assert(Q.size() == 6); assert(Q.top() == 8); Q.pop(); assert(Q.top() == 7); Q.pop(); assert(Q.top() == 5); Q.pop(); assert(Q.top() == 4); Q.pop(); assert(Q.top() == 2); Q.pop(); assert(Q.top() == 1); Q.pop(); assert(Q.empty()); } STL Priority Queues ? Element type with priority ?<typename T> t ?Compare & cmp ? Associative queue operations ?Void push(t) ?void pop() ?T& top() ?void clear() ?bool empty() 3 Priority Queue Implementation ? Implement as adaptor class around ?Linked lists ?Binary Search Trees ?B-Trees ?Heaps ?This is what we’ll study ?O( logN ) worst case for both insertion and delete operations Partially Ordered Trees ?Definition: A partially ordered tree is a tree T such that: ?There is an order relation >= defined for the vertices of T ?For any vertex p and any child c of p, p >= c Partially Ordered Trees ?Consequences: ?The largest element in a partially ordered tree is the root ?No conclusion can be drawn about the order of children Heaps ?Definition: A heap is a partially ordered, complete, binary tree ?The tree is completely filled on all levels except possibly the lowest 4 3 2 1 0 root Heap example ? Parent of v[k] = v[(k-1)/2] ? Left child of v[k] = v[2*k+1] ? Right child of v[k] = v[2*k + 2] 13 12 11 10 9 8 7 6 5 4 3 2 1 0 J I H G F E D C B A A B C D E F G H I J The Push-Heap Algorithm ? Add new data at next leaf ? Repair upward ? Repeat ? Locate parent ? if tree not partially ordered ? swap ? else ? stop ? Until partially ordered Page 4 1 Priority Queues Sections 6.1 to 6.5 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] R l r ll lr rr rl root Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] ll r l R 6 5 4 3 2 1 0 2 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] lr ll r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] rl lr ll r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] rr rl lr ll r l R 6 5 4 3 2 1 0 Priority Queue Note: STL provides deleteMax. But book provides deleteMin. We’ll follow the deleteMax strategy. deleteMax Priority Queue Usage int main() { priority_queue<int> Q; Q.push(1); Q.push(4); Q.push(2); Q.push(8); Q.push(5); Q.push(7); assert(Q.size() == 6); assert(Q.top() == 8); Q.pop(); assert(Q.top() == 7); Q.pop(); assert(Q.top() == 5); Q.pop(); assert(Q.top() == 4); Q.pop(); assert(Q.top() == 2); Q.pop(); assert(Q.top() == 1); Q.pop(); assert(Q.empty()); } STL Priority Queues ? Element type with priority ?<typename T> t ?Compare & cmp ? Associative queue operations ?Void push(t) ?void pop() ?T& top() ?void clear() ?bool empty() 3 Priority Queue Implementation ? Implement as adaptor class around ?Linked lists ?Binary Search Trees ?B-Trees ?Heaps ?This is what we’ll study ?O( logN ) worst case for both insertion and delete operations Partially Ordered Trees ?Definition: A partially ordered tree is a tree T such that: ?There is an order relation >= defined for the vertices of T ?For any vertex p and any child c of p, p >= c Partially Ordered Trees ?Consequences: ?The largest element in a partially ordered tree is the root ?No conclusion can be drawn about the order of children Heaps ?Definition: A heap is a partially ordered, complete, binary tree ?The tree is completely filled on all levels except possibly the lowest 4 3 2 1 0 root Heap example ? Parent of v[k] = v[(k-1)/2] ? Left child of v[k] = v[2*k+1] ? Right child of v[k] = v[2*k + 2] 13 12 11 10 9 8 7 6 5 4 3 2 1 0 J I H G F E D C B A A B C D E F G H I J The Push-Heap Algorithm ? Add new data at next leaf ? Repair upward ? Repeat ? Locate parent ? if tree not partially ordered ? swap ? else ? stop ? Until partially ordered 4 The Push Heap Algorithm ?Add new data at next leaf rr rl lr ll r l R 7 6 5 4 3 2 1 3 4 5 6 7 The Push Heap Algorithm ?Add new data at next leaf 8 3 4 5 6 7 rr rl lr ll r l R 7 6 5 4 3 2 1 The Push Heap Algorithm ?Repeat ?Locate parent of v[k] = v[(k – 1)/2] ?if tree not partially ordered ?swap ?else ?stop 8 3 4 5 6 7 rr rl lr ll r l R 6 5 4 3 2 1 0 The Push Heap Algorithm ?Repeat ?Locate parent of v[k] = v[(k – 1)/2] ?if tree not partially ordered ?swap ?else ?stop 8 3 4 5 6 7 rr rl lr ll r l R 6 5 4 3 2 1 0 The Push Heap Algorithm ?Repeat ?Locate parent of v[k] = v[(k – 1)/2] ?if tree not partially ordered ?swap ?else ?stop 5 3 4 8 6 7 rr rl lr ll r l R 6 5 4 3 2 1 0 The Push Heap Algorithm ?Repeat ?Locate parent of v[k] = v[(k – 1)/2] ?if tree not partially ordered ?swap ?else ?stop 5 3 4 8 6 7 rr rl lr ll r l R 6 5 4 3 2 1 0 Page 5 1 Priority Queues Sections 6.1 to 6.5 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] R l r ll lr rr rl root Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] ll r l R 6 5 4 3 2 1 0 2 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] lr ll r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] rl lr ll r l R 6 5 4 3 2 1 0 Vector Representation of Complete Binary Tree ?v[k].parent == v[(k-1)/2] ?v[k].lchild == v[2*k+1] ?v[k].rchild == v[2*k+2] rr rl lr ll r l R 6 5 4 3 2 1 0 Priority Queue Note: STL provides deleteMax. But book provides deleteMin. We’ll follow the deleteMax strategy. deleteMax Priority Queue Usage int main() { priority_queue<int> Q; Q.push(1); Q.push(4); Q.push(2); Q.push(8); Q.push(5); Q.push(7); assert(Q.size() == 6); assert(Q.top() == 8); Q.pop(); assert(Q.top() == 7); Q.pop(); assert(Q.top() == 5); Q.pop(); assert(Q.top() == 4); Q.pop(); assert(Q.top() == 2); Q.pop(); assert(Q.top() == 1); Q.pop(); assert(Q.empty()); } STL Priority Queues ? Element type with priority ?<typename T> t ?Compare & cmp ? Associative queue operations ?Void push(t) ?void pop() ?T& top() ?void clear() ?bool empty() 3 Priority Queue Implementation ? Implement as adaptor class around ?Linked lists ?Binary Search Trees ?B-Trees ?Heaps ?This is what we’ll study ?O( logN ) worst case for both insertion and delete operations Partially Ordered Trees ?Definition: A partially ordered tree is a tree T such that: ?There is an order relation >= defined for the vertices of T ?For any vertex p and any child c of p, p >= c Partially Ordered Trees ?Consequences: ?The largest element in a partially ordered tree is the root ?No conclusion can be drawn about the order of children Heaps ?Definition: A heap is a partially ordered, complete, binary tree ?The tree is completely filled on all levels except possibly the lowest 4 3 2 1 0 root Heap example ? Parent of v[k] = v[(k-1)/2] ? Left child of v[k] = v[2*k+1] ? Right child of v[k] = v[2*k + 2] 13 12 11 10 9 8 7 6 5 4 3 2 1 0 J I H G F E D C B A A B C D E F G H I J The Push-Heap Algorithm ? Add new data at next leaf ? Repair upward ? Repeat ? Locate parent ? if tree not partially ordered ? swap ? else ? stop ? Until partially ordered 4 The Push Heap Algorithm ?Add new data at next leaf rr rl lr ll r l R 7 6 5 4 3 2 1 3 4 5 6 7 The Push Heap Algorithm ?Add new data at next leaf 8 3 4 5 6 7 rr rl lr ll r l R 7 6 5 4 3 2 1 The Push Heap Algorithm ?Repeat ?Locate parent of v[k] = v[(k – 1)/2] ?if tree not partially ordered ?swap ?else ?stop 8 3 4 5 6 7 rr rl lr ll r l R 6 5 4 3 2 1 0 The Push Heap Algorithm ?Repeat ?Locate parent of v[k] = v[(k – 1)/2] ?if tree not partially ordered ?swap ?else ?stop 8 3 4 5 6 7 rr rl lr ll r l R 6 5 4 3 2 1 0 The Push Heap Algorithm ?Repeat ?Locate parent of v[k] = v[(k – 1)/2] ?if tree not partially ordered ?swap ?else ?stop 5 3 4 8 6 7 rr rl lr ll r l R 6 5 4 3 2 1 0 The Push Heap Algorithm ?Repeat ?Locate parent of v[k] = v[(k – 1)/2] ?if tree not partially ordered ?swap ?else ?stop 5 3 4 8 6 7 rr rl lr ll r l R 6 5 4 3 2 1 0 5 The Push Heap Algorithm ?Repeat ?Locate parent of v[k] = v[(k – 1)/2] ?if tree not partially ordered ?swap ?else ?stop 5 3 4 8 6 7 rr rl lr ll r l R 6 5 4 3 2 1 0 The Push Heap Algorithm ?Repeat ?Locate parent of v[k] = v[(k – 1)/2] ?if tree not partially ordered ?swap ?else ?stop 5 3 4 7 6 8 rr rl lr ll r l R 6 5 4 3 2 1 0 The Pop-Heap Algorithm ?Copy last leaf to root ?Remove last leaf ?Repeat ?find the larger child ?if not partially ordered tree ?swap ?else ?stop ?Until tree is partially ordered The Pop Heap Algorithm ?Copy last leaf to root 5 3 4 7 6 8 rr rl lr ll r l R 6 5 4 3 2 1 0 The Pop Heap Algorithm ?Copy last leaf to root 5 3 4 7 6 5 rr rl lr ll r l R 6 5 4 3 2 1 0 The Pop Heap Algorithm ?Remove last leaf 3 4 7 6 5 rr rl lr ll r l R 6 5 4 3 2 1 0Read More

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