问题标签 [priority-queue]

我需要实现一个优先级队列，其中队列中项目的优先级可以更改，并且队列会自行调整，以便始终以正确的顺序删除项目。我对如何实现它有一些想法，但我确信这是一个相当常见的数据结构，所以我希望我可以使用比我更聪明的人的实现作为基础。

谁能告诉我这种优先级队列的名称，以便我知道要搜索什么，或者更好的是，为我指出一个实现？

PriorityBlockingQueue是无界的，但我需要以某种方式绑定它。实现这一目标的最佳方法是什么？

有关信息，有界PriorityBlockingQueue将用于ThreadPoolExecutor.

注意：如果发生这种情况，我不想抛出异常，我想将对象放入队列中，然后根据其优先级值将其剪切。有什么好的方法来做这个切东西吗？

我正在编写霍夫曼编码。这是我的程序的开始：

程序首先输出字符及其出现次数。这看起来不错：

但是必须按优先级顺序显示节点内容的测试循环输出：

这不是预期的顺序。为什么？

情况：模拟环境中有几个实体，它们有一个人为的时间概念，称为“滴答声”，与实时没有联系。每个实体轮流移动，但有些比其他实体更快。这以延迟表示，以滴答为单位。所以实体 A 可能有 10 的延迟，而 B 可能有 25 的延迟。在这种情况下，轮流顺序将变为：

AABAA

我想知道使用什么数据结构。起初我自动想到“优先队列”，但延迟与“当前时间”相关，这使事情变得复杂。此外，会有更大延迟的实体，并且程序将运行数百万个滴答并不是不可预见的。当延迟本身保持相对较小且不增加时，内部计数器越来越高似乎很愚蠢。

那么你将如何解决这个问题？

如果是，那么为什么优先队列是非线性数据结构？与线性数据结构相比，非线性数据结构的性能是否较差？如果是，那为什么？请详细说明。

默认的 stl 优先级队列是 Max one（Top 函数返回最大元素）。

说，为简单起见，它是 int 值的优先级队列。

我需要一个优先级队列，我可以在其中增加或减少优先级键。所以 boost::mutable_queue 尽管缺乏文档，但似乎很完美。

问题是我需要在某个时候迭代队列中的所有元素。我怎样才能做到这一点？

或者是否有其他可以工作的数据结构（最好是在 boost 中）？

如果这是一个尝试过的问题，请原谅我，但我很难弄清楚。

我目前有一个类节点，每个“节点”都是迷宫中的一个正方形。我正在尝试实现 A* 算法，因此每个节点内部都有一个 f-cost (int) 数据成员。我想知道是否有一种方法可以创建这些节点的优先级队列，并将 f-cost 变量设置为比较器？

我看过网上的例子，但我能找到的只是字符串优先级队列。我可以为 Node 类实现 Comparator 吗？这是否允许我访问存储在其中的数据成员？

非常感谢！

我需要某种优先级队列来存储对<key, value>。值是唯一的，但键不是。我将执行以下操作（最常见的首先）：

1. 随机插入；
2. 检索（并删除）具有最少键的所有元素。
3. 随机删除（按值）；

我不能使用std::priority_queue，因为它只支持移除头部。

目前，我使用的是未排序的std::list. 插入是通过将新元素推到后面来执行的 (O(1))。操作 2list::sort在执行实际检索之前使用 (O(N*logN))对列表进行排序。然而，去除是 O(n)，这有点贵。

有更好的数据结构的想法吗？

我正在编写一个查询处理器，它分配大量内存并尝试查找匹配的文档。每当我找到匹配项时，我都会创建一个结构来保存描述文档的两个变量并将其添加到优先级队列中。由于无法知道我会这样做多少次，我尝试使用 new 动态创建我的结构。当我从优先级队列中弹出一个结构时，队列（STL 优先级队列实现）应该调用对象的析构函数。我的结构代码没有析构函数，所以我假设在这种情况下会调用默认析构函数。

但是，我第一次尝试创建 DOC 结构时，出现以下错误：

QueryProcessor.exe 中 0x7c812afb 处的未处理异常：Microsoft C++ 异常：内存位置 0x0012f5dc 处的 std::bad_alloc..

我不明白发生了什么 - 我是否用尽了太多内存以至于堆已满？似乎不太可能。而且好像我以前什至没有使用过那个指针。

所以：首先，我在做什么导致错误，其次，以下代码会多次工作吗？我是否需要为每个创建的结构创建一个单独的指针，或者我可以重复使用相同的临时指针并假设队列将保留一个指向每个结构的指针？

这是我的代码：

非常感谢，bsg。