STL Priority queue with custom comparator not working as expected

I'm trying to implement Priority queue with custom operator. The algorithm tries to find the minimum increments to be done so that no two adjacent elements in array have absolute difference > 1.
For this, I get the maximum element "x" in the array and modify its neighbours to x-1, then repeat the same for other elements
Here's the code:

#include<iostream>  #include<algorithm>  #include<vector>  #include<queue>  using namespace std;    int arr[100], visited[100];  int sizeOfArray;  struct comp  {  public:      bool operator() (int x1, int x2) {      return arr[x1] < arr[x2];      }  };      int main(){      cin>>sizeOfArray;      priority_queue<int, vector<int>, comp> priorityQue;      for(int i = 0; i < sizeOfArray; i++) {          cin>>arr[i];          priorityQue.push(i);          visited[i]=0;      }      while(!priorityQue.empty()) {          int index = priorityQue.top();          priorityQue.pop();          if(visited[index])                 continue;          visited[index]=1;            cout<<"Currently at index: "<<index<<endl;            int currentElement = arr[index];          int dx[] = {-1, 1};    // left and right neighbours          for(int k = 0; k < 2; k++) {              int nextIndex = index + dx[k];              if( nextIndex >= 0 && nextIndex < sizeOfArray &&                   (currentElement - arr[nextIndex]) > 1 )               {                  arr[nextIndex] = currentElement - 1;                  cout<<"Modifying index :"<<nextIndex<<endl;                  cout<<"New Array is: ";                  // print array                   for(int z=0;z<sizeOfArray;z++)                      cout<<arr[z]<<" ";                  cout<<endl;                                    priorityQue.push(nextIndex);                  cout<<"Pushing index "<<nextIndex<<" to queue"<<endl;              }          }      }      return 0;  }  

For the input:

4
4 1 1 0

The Output is:

Currently at index: 0
Modifying index :1
New Array is: 4 3 1 0
Pushing index 1 to queue
Currently at index: 2
Currently at index: 1
Modifying index :2
New Array is: 4 3 2 0
Pushing index 2 to queue
Currently at index: 3

I found that priority queue is not extracting the maximum element as per the comparator as it should be. After visiting index 0, array becomes 4 3 1 0 hence index 1 should come next but in this case index 2 is picked up. What am I missing??

https://stackoverflow.com/questions/66738914/stl-priority-queue-with-custom-comparator-not-working-as-expected March 22, 2021 at 08:19AM