具有自定义比较器的 STL 优先级队列未按预期工作

Question

我正在尝试使用自定义运算符实现优先级队列。该算法试图找到要完成的最小增量，以便数组中没有两个相邻元素的绝对差 > 1。
为此，我获取数组中的最大元素“x”并将其邻居修改为 x-1，然后对其他元素重复相同的操作
这是代码：

#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;
}

对于输入：

4
4 1 1 0

输出是：

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

我发现优先队列没有按照比较器提取最大元素，这是应该的。访问索引 0 后，数组变为 4 3 1 0 因此索引 1 应该是下一个，但在这种情况下，索引 2 被拾取。我错过了什么？？

Answer 1

您在将项目放入队列并且仍然是该队列的一部分后对其进行修改。这不受优先级队列的支持并且会产生未指定的结果。 C++ STL 不提供可更新的优先级队列。

但是，看到您的用例，我怀疑这是竞争性算法编程。这个用例有不错的选择。 我不会推荐它们用于生产代码（至少在没有适当的抽象的情况下是这样。

第一个“正确”的替代方法是使用 std::set<std::pair<...>>。您的代码将保持非常相似，但存在一些重要差异：

您不需要自定义比较器，而是依靠成对比较（您需要使用 std::greater 作为比较器才能将最大的项目放在“顶部”，
你会把{a[index], index}作为这个集合的元素，
您将使用 .begin() 而不是 .top(),
您需要 .erase() 个项目才能更新它们的值，然后用新值再次插入它们。

我相信以上与优先级队列的标准实现具有相同的复杂性。尽管更新看起来很慢，但我们只进行了两次 O(log n) 操作——这与堆结构中的实际更新的复杂性相同。

您可以像示例中那样使用间接比较器来实现它。通常它会起作用，但您仍然需要围绕更新进行擦除和插入流程。此外，您还需要比较比较器中的索引，以便使具有相同优先级的项目不同，以便删除正确的项目。

此外，在许多常见情况下，我们还可以使用另一种技巧，例如 Dijkstra 或 Prim 算法。在这些情况下，我们只会将优先级更新为更高（更低的值）。在这种情况下，我们可以忽略擦除项目，而只是添加重复项。这是可行的，因为单个 query/update 的时间复杂度变为 O(log n^2) = O(2 log n) = O(log n)。内存复杂度增加，但这通常不是问题。

在最后一种情况下，您可以根据自己的喜好使用其他容器，std::priority_queue<std::pair<...>> 或 std::multimap<...> 都可以很好地工作。但是在所有这些中，您需要将优先级作为插入项目的一部分，而不是通过间接比较器使用它。

作为附录，这是您的代码，经过更改后可以按预期工作：

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

int arr[100], visited[100];
int sizeOfArray;


int main(){
    cin>>sizeOfArray;
    priority_queue<std::pair<int, int>> priorityQue;
    for(int i = 0; i < sizeOfArray; i++) {
        cin>>arr[i];
        priorityQue.push({arr[i], i});
        visited[i]=0;
    }
    while(!priorityQue.empty()) {
        int index = priorityQue.top().second;
        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({arr[nextIndex], nextIndex});
                cout<<"Pushing index "<<nextIndex<<" to queue"<<endl;
            }
        }
    }
    return 0;
}

具有自定义比较器的 STL 优先级队列未按预期工作

STL Priority queue with custom comparator not working as expected

c++

algorithm

stl

priority-queue

max-heap