如何告诉std :: priority_queue刷新它的排序？

Question

我有一个指向a的优先级队列struct city.我修改优先级队列外的这些指针指向的对象,并希望告诉优先级队列根据新值"重新排序"自己.

我该怎么办？

例:

#include <iostream>
#include <queue>

using namespace std;

struct city {
    int data;
    city *previous;
};

struct Compare {
    bool operator() ( city *lhs, city *rhs )
    {
        return ( ( lhs -> data ) >= ( rhs -> data ) );
    }
};

typedef priority_queue< city *, vector< city * >, Compare > pqueue;

int main()
{
    pqueue cities;

    city *city1 = new city;
    city1 -> data = 5;
    city1 -> previous = NULL;
    cities.push( city1 );

    city *city2 = new city;
    city2 -> data = 3;
    city2 -> previous = NULL;
    cities.push( city2 );

    city1 -> data = 2;
    // Now how do I tell my priority_queue to reorder itself so that city1 is at the top now?

    cout << ( cities.top() -> data ) << "\n";
    // 3 is printed :(

    return 0;
}

Answer 1

基于http://www.sgi.com/tech/stl/priority_queue.html,看起来没有办法做到这一点,没有清空和重新插入.

如果你愿意离开priority_queue(但仍然想要一个堆),那么你可以使用一个向量,以及make_heap,push_heap和pop_heap.请参阅页面中的notes部分,了解priority_queue.

Answer 2

如果需要保留有序集合,可以考虑以下解决方案:使用std::set和更新值删除项目,更新其值并将其放回集合中.这将为您提供更新一个项目的O(log n)复杂度,这是在通常的堆结构中最好的(假设您可以使用筛选筛选程序访问其内部组件).唯一的缺点std::set是初始化具有n个项目的集合的时间.(O(n log n)代替O(n)).

Answer 3

这有点hackish,但没有任何违法行为,它完成了工作.

std::make_heap(const_cast<city**>(&cities.top()),
               const_cast<city**>(&cities.top()) + cities.size(),
               Compare());

更新:

如果出现以下情况,请勿使用此黑客

• 底层容器不是vector.
• 该Compare函子的行为,将导致您的外部副本的顺序的不同副本Compare里面存放的priority_queue.
• 您不完全了解这些警告的含义.

您始终可以编写自己的容器适配器来包装堆算法. priority_queue只不过是一个简单的包装make/push/pop_heap.