问题标签 [priority-queue]

我正在研究一个查询处理器，它从内存中读取长长的文档 ID 列表并查找匹配的 ID。当它找到一个时，它会创建一个包含 docid（一个 int）和文档的排名（一个 double）的 DOC 结构，并将其推送到优先级队列中。我的问题是，当搜索的单词有很长的列表时，当我尝试将 DOC 推送到队列时，出现以下异常： QueryProcessor.exe 中 0x7c812afb 处的未处理异常：Microsoft C++ 异常：std： :bad_alloc 在内存位置 0x0012ee88..

当单词有一个简短的列表时，它可以正常工作。我尝试在代码中的多个位置将 DOC 推送到队列中，它们都可以工作到某一行；之后，我收到上述错误。我完全不知道出了什么问题，因为读入的最长列表小于 1 MB，并且我释放了我分配的所有内存。当我尝试将 DOC 推送到有容量容纳它的队列上时，为什么会突然出现 bad_alloc 异常（我使用了一个保留了足够空间的向量作为优先级队列的底层数据结构）？

我知道如果不看所有代码几乎不可能回答这样的问题，但是在这里发布太长了。我正在尽我所能，并焦急地希望有人能给我一个答案，因为我无能为力。

NextGEQ 函数逐块读取压缩的 docid 块列表。也就是说，如果它发现块中的 lastdocid（在一个单独的列表中）大于传入的 docid，它会解压块并搜索，直到找到正确的。每个列表都以关于列表的元数据开始，其中包含每个压缩块的长度和块中的最后一个 docid。data.iquery 指向元数据的开头；data.metapointer 指向元数据中函数当前所在的位置；并且 data.blockpointer 指向未压缩 docid 块的开头，如果有的话。如果它看到它已经解压缩，它只是搜索。下面，当我第一次调用该函数时，它解压了一个块并找到了docid；之后推送到队列中。第二次，它没有 甚至需要解压；也就是说，没有分配新的内存，但在那之后，推送到队列会产生一个 bad_alloc 错误。

编辑：我清理了我的代码，以便它应该编译。我还添加了 OpenList() 和 NextGEQ 函数，虽然后者很长，因为我认为问题是由其中某处的堆损坏引起的。非常感谢！

非常感谢，bsg。

我正在尝试按升序排列整数对，其中如果两个条目都严格小于另一对的条目，则认为一对小于另一对，如果两个条目都严格大于另一对的条目，则大于另一对一对。所有其他情况都被认为是无法比拟的。

我想解决这个问题的方法是通过定义Comparator实现上述内容的 a ，但会在无法比较的情况下抛出异常，并将其提供给 a PriorityQueue。当然，在插入一对优先级队列时，会进行多次比较，同时将新条目冒泡到堆中的正确位置，其中许多是可比较的。但是在冒泡过程中可能会遇到与这个新的pair无法比较的pair，会抛出异常。如果发生这种情况，该状态将是PriorityQueue什么？我试图插入的这对是否会在抛出异常之前位于堆中的最后一个位置？如果我使用该PriorityQueue's remove(Object o)方法，是否PriorityQueue会恢复到一致的状态？

谢谢

在 C++ 标准库文档中搜索某些函数时，我读到优先级队列的推送和弹出需要恒定的时间。

http://www.cplusplus.com/reference/stl/priority_queue/push/

常量（在 priority_queue 中）。尽管请注意 push_heap 以对数时间运行。

我的问题是使用什么样的数据结构来维护优先级队列，其中 O(1) 用于 push 和 pop ？

其中 PriorityNode 定义为：

我在这里使用比较器并实现优先级队列时遇到了很多困难 - 请指出我正确的方向。

我刚刚完成了一个复杂的工作分配应用程序的编码，其中很多工作都是使用优先级队列完成的。然而，当我部署时，我发现 Web 服务器运行的是 PHP 5.2。

是否有 PHP<5.3 的实现可以作为 SPLPriorityQueue 的替代品？

尝试将对象添加到优先级队列时，我不断收到空指针异常

我初始化队列：

在这里我尝试添加：

为什么这不起作用？我知道我的 NodeObject 不为空，因为我在添加它之前就创建了它。

哪个实现不那么“重”：PriorityQueue 或排序的 LinkedList（使用比较器）？

我想对所有项目进行排序。插入将非常频繁，有时我将不得不运行所有列表来进行一些操作。

我可以使用 Collections.binarySearch() 方法来搜索 PriorityQueue 中的元素吗？否则，如何将搜索算法应用于 PriorityQueue？

我有这个（Evento 类实现 Comparable）：

我得到了这个错误：“集合类型中的方法 binarySearch(List>, T) 不适用于参数 (PriorityQueueCAP, Evento)”

为什么？

提前致谢！

我有一个接受传入查询并执行它们的服务器应用程序。如果查询太多，则应将它们排队，并且如果执行了其他一些查询，则也应执行排队的查询。由于我想传递具有不同优先级的查询，我认为使用 priority_queue 将是最佳选择。

例如，接受查询的数量（a）达到限制，新查询将存储在队列中。如果来自 (a) 的一些查询被执行，则所有查询的优先级为 1（最低），程序将从队列中选择具有最高优先级的查询并执行它。仍然没有问题。现在有人正在发送一个优先级为 5 的查询，该查询被添加到队列中。由于这是具有最高优先级的查询，一旦运行的查询不再达到限制，应用程序就会执行此查询。最坏的情况可能是 500 个优先级为 1 的查询排队但不会执行，因为有人总是发送优先级为 5 的查询，因此这 500 个查询将排队很长时间。为了防止我想增加所有查询的优先级，这些查询的优先级低于优先级较高的查询，在这个例子中，优先级低于 5。所以如果优先级为 5 的查询被拉出队列中所有其他优先级 < 5 的查询应增加 0.2。这样，即使可能有 100 个具有更高优先级的查询，低优先级的查询也不会永远排队。

我真的希望有人可以帮助我解决优先级问题：

由于我的查询由一个对象组成，我认为这样的事情可能会起作用：

这不是家庭作业。

我正在使用一个小的“优先队列”（目前实现为数组）来存储具有最小值的最后 N 个项目。这有点慢 - O(N) 项插入时间。当前的实现跟踪数组中最大的项目并丢弃任何不适合数组的项目，但我仍然想进一步减少操作数量。

寻找符合以下要求的优先级队列算法：

1. 队列可以实现为数组，它具有固定大小并且_不能_增长。严格禁止在任何队列操作期间进行动态内存分配。
2. 任何不适合数组的东西都会被丢弃，但队列会保留所有遇到过的最小元素。
3. O(log(N)) 插入时间（即，将元素添加到队列中应该占用 O(log(N))）。
4. （可选）O(1) 访问队列中*最大* 的项目（队列存储 *最小* 项目，因此最大的项目将首先被丢弃，我需要它们来减少操作次数）
5. 易于实施/理解。理想情况下——类似于二分搜索——一旦你理解了它，你就会永远记住它。
6. 元素不需要以任何方式排序。我只需要保持 N 曾经遇到过的最小值。当我需要它们时，我会立即访问所有这些。所以从技术上讲，它不必是一个队列，我只需要存储 N 个最后的最小值。

我最初考虑使用二进制堆（它们可以通过数组轻松实现），但显然当数组不能再增长时它们表现不佳。链表和数组需要额外的时间来移动东西。stl 优先级队列增长并使用动态分配（不过我可能错了）。

那么，还有其他想法吗？

--EDIT--
我对 STL 的实现不感兴趣。由于大量的函数调用，STL 实现（由少数人建议）的工作速度比当前使用的线性数组慢一些。

我对优先队列算法感兴趣，而不是实现。