How does a priority queue compare and store values during a push operation?
I was working on a Priority queue and I wanted to test how the values are compared using a comparable class. This was my code.
#include <iostream>
#include <queue>
using namespace std;
class g {
public:
bool operator() (int a, int b) {
cout<<a<<" "<<b<<endl;
return (a > b);
}
};
int main() {
priority_queue<int,vector<int>,g> p;
p.push(2);
cout<<"CHECK1"<<endl;
p.push(4);
cout<<"CHECK2"<<endl;
p.push(8);
cout<<"CHECK3"<<endl;
p.push(1);
cout<<"CHECK4"<<endl;
while(!p.empty()) {
cout<<p.top()<<endl;
p.pop();
}
}
The way out was
CHECK1
2 4
CHECK2
2 8
CHECK3
4 1
2 1
CHECK4
1
8 2
2 4
2
4 8
4
8
I see that when 4 is inserted it is compared to 2 and when 8 is inserted it is compared to 2. But why was 8 not compared to 4? Can anyone please help?
source to share
The priority queue is usually implemented as a perfectly balanced heap structure. The heap can be thought of as a binary tree with the only requirement that the priority of the root be higher (lower value for your comparator) than its children, the state of the heap.
root
Lchild1 Rchild1
Lchild2 Rchild2 Lchild2 empty
Any inserts are inserted in an empty space to keep the tree in balance. After insertion, it moves up the tree to maintain heap state. So in this case only comparisons with Rchild1 and root are possible.
Deletion / pop () is done by removing the root and replacing in Lchild2 to maintain perfect balance, then moving Lchild2 down the heap to fix the heap state.
This tree is easily stored in a vector.
root(2)
Lchild1(4) empty.
Box 8 (in the blank space) should only be compared to the root.
root(2)
Lchild1(4) Rchild1(8).
empty
Insert 1 into blank space, need to check 4 and swap, then compare against root (and swap).
There are many possible internal representations, see for example https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/pq_performance_tests.html . Others include the red-black tree.
This might also help Efficiency STL priority_queue
source to share
std::priority_queue<...>
internally represented as d-heap . The view uses a tree where the root of each subtree has the highest priority in that subtree. It is structured to minimize the number of comparisons required.
When an element is inserted, it is inserted at the bottom of the tree and exchanged with its parents along the path to the root if it has a higher priority. Deletion swaps the root with the leaf, deletes the leaf, and then swaps the root with the highest priority of the child of the subtree while it has a lower priority.
source to share