允许密钥增加的可变优先级队列

当实现图搜索算法时，我需要一个允许优先级更改的优先级队列。到目前为止，我一直在使用（detail命名空间，因此没有记录），但只是被告知它没有定义优先级增加（我现在看到的也是在concept documentation中提到的）。允许密钥增加的可变优先级队列

所以，我需要找到一个允许增加和减少的结构。我已经尝试使用vector和push_heap/pop_heap/make_heap，但更新速度太慢。有什么选择？我看到助推在待处理（同样没有记录的）目录中有两个类，mutable_queue和relaxed_heap，但我只能在五年前的maillist线索中找到它们。他们之间有什么区别，他们是否允许增加和减少？有没有任何实施方案未被接受？

来源

2011-09-06 carlpett

Boost.MultiIndex库的特性容器的操作对象的状态为update，并相应地更新索引。

在你的情况下，modify成员函数似乎适合。从文档：

struct change_name 
{ 
    change_name(const std::string& new_name):new_name(new_name){} 

    void operator()(employee& e) 
    { 
    e.name=new_name; 
    } 

private: 
    std::string new_name; 
}; 

typedef employee_set::index<name>::type employee_set_by_name; 
employee_set_by_name& name_index = es.get<name>(); 

employee_set_by_name::iterator it = name_index.find("Anna Jones"); 
name_index.modify(it,change_name("Anna Smith"));

来源

2011-09-06 07:12:32

将该值放入堆中。您只需修改该值，然后通过向上或向下冒泡来恢复堆不变量。

回想一下，堆本质上是一个二叉树，其中每个节点都大于它的两个子节点。

所以，如果你增加一个节点的值，你检查它是否已经大于其父如果是交换它们，然后重复拉节点向树根直到节点不再需要交换。

如果你减少了一个节点的值，那么如果你现在小于你的两个孩子中最大的一个交换。重复将节点推向树叶，直至不再需要交换。

来源

2011-09-06 07:10:10

感谢您的意见。然而，我并不太热衷于自己实现它 - 我强烈怀疑我会创建一个比boost开发者更有效的结构，并且它将用于我的程序的主要部分，因此性能相当重要。你知道任何现有的，经过实地验证的建议吗？ – carlpett

允许密钥增加的可变优先级队列

回答

相关问题