Priority Queues Notes | EduRev

: Priority Queues Notes | EduRev

 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 0
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!