How does Priority queue compare and store the values during the push operation?

Question

I was working on Priority queue and I wanted to check how the values are compared using the 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 output 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 pushed in, it gets compared with 2 and when 8 is pushed in, it gets compared with 2 again. But why was 8 not compared with 4? Can anyone please help?

Answer 1

A priority queue is commonly implemented as a perfectly balanced heap structure. The heap can be seen as a binary tree with the only requirement that the priority of the root is higher(smaller value for your comparator) than its children, the heap condition.

                root
      Lchild1             Rchild1
  Lchild2  Rchild2     Lchild2  empty

Any inserts are inserted at the empty spot to keep the tree in balance. After the insert it is moved up the tree to maintain the heap condition. So in this case the only comparisons possible is to Rchild1 and root.

Deletion/pop() is done by removing the root and swapping in Lchild2, to maintain perfect balance, then moving Lchild2 down the heap to corrrect the heap condition.

This tree is easily kept in a vector.

                root(2)
      Lchild1(4)        empty.

The insert of 8 (in the empty spot) only needs to compare to the root.

                root(2)
      Lchild1(4)        Rchild1(8).
   empty

The insert of 1 in the empty spot, needs to check the 4 and swap, then compare to the root (and swap).

There are quite a few possible internal representations, see for instance https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/pq_performance_tests.html. Others include a Red-Black tree.

This might also help Efficiency of the STL priority_queue

Answer 2

The std::priority_queue<...> is internally represented as a d-heap. The representation uses a tree where the root of each subtree has the highest priority in this subtree. It is structured to minimize the number of necessary comparisons.

When inserting an element it is inserted at the bottom of the tree and exchanged with parents along the path to the root as long as it has higher priority. Removal exchanges the root with a leaf, removes the leaf, and then exchanges the root with the highest priority child of the subtree it is at as long as it has lower priority.