问题标签 [priority-queue]

我正在寻找优先级队列或堆数据结构的 .NET 实现

优先队列是比简单排序提供更多灵活性的数据结构，因为它们允许新元素以任意间隔进入系统。将新作业插入优先级队列比在每次到达时重新排序所有内容更具成本效益。

基本优先级队列支持三个主要操作：

• 插入（Q，x）。给定一个带有键 k 的项目 x，将其插入优先级队列 Q。
• 查找最小值 (Q)。返回指向其键值小于优先级队列 Q 中任何其他键的项的指针。
• 删除-最小值（Q）。从优先级队列 Q 中移除 key 最小的 item

除非我找错了地方，否则框架中没有一个。有人知道一个好的，还是我应该自己推出？

我有一个 IBM WebSphere MQ 队列（在 Windows 上运行），其中包含许多不同优先级的项目。

我目前使用总深度计数，mqQueue.CurrentDepth但我想计算队列中每个优先级的项目数。

知道如何实现这一目标吗？

更新：这是我对 Hashed Timing Wheels 的实现。如果您有提高性能和并发性的想法，请告诉我。（2009 年 1 月 20 日）

更新：我通过使用Hierarchical 和 Hashed Timing Wheels解决了这个问题。（2009 年 1 月 19 日）

我正在尝试在 Java 中实现一个特殊用途的计时器，该计时器针对超时处理进行了优化。例如，用户可以注册一个带有截止期限的任务，并且计时器可以在截止期限结束时通知用户的回调方法。在大多数情况下，注册的任务会在很短的时间内完成，因此大多数任务将被取消（例如 task.cancel()）或重新安排到未来（例如 task.rescheduleToLater(1, TimeUnit.SECOND)） .

我想使用这个计时器来检测空闲的套接字连接（例如，在 10 秒内没有收到消息时关闭连接）和写入超时（例如，当写入操作在 30 秒内未完成时引发异常。）在大多数情况下，不会发生超时，客户端将发送一条消息并发送响应，除非存在奇怪的网络问题..

我不能使用 java.util.Timer 或 java.util.concurrent.ScheduledThreadPoolExecutor 因为他们认为大多数任务都应该超时。如果一个任务被取消，被取消的任务被存储在它的内部堆中，直到 ScheduledThreadPoolExecutor.purge() 被调用，这是一个非常昂贵的操作。（O（NlogN）也许？）

在我在 CS 课程中学到的传统堆或优先级队列中，在许多情况下更新元素的优先级是一项昂贵的操作 (O(logN)，因为它只能通过删除元素并重新插入它来实现新的优先级值。像斐波那契堆这样的堆有 O(1) 时间的 reductionKey() 和 min() 操作，但我至少需要快速 increaseKey() 和 min()（或 reductionKey() 和 max()） .

您是否知道针对此特定用例高度优化的任何数据结构？我正在考虑的一种策略是将所有任务存储在哈希表中并每秒左右迭代所有任务，但这并不是那么漂亮。

我正在实现一个小队列来处理哪个进程首先运行。我正在使用数据库中的表来执行此操作。这是表的结构（我在 SQLite 中模拟它）：

我正在尝试编写 SQL 来给我接下来可以运行哪个进程的行。以下是一些示例数据：

如果我使用这个 SQL，我可以按正确的顺序获取数据：

这将为我提供顶部具有最低优先级编号（最重要）的项目，并且在这些优先级编号中，最早进入队列（按时间戳）在顶部。

我可以运行此查询，并且只获取第一行，但我宁愿使用 SQL 查询来执行此操作，该查询将为我提供位于队列顶部的进程的一行（在上面的示例数据中，行id=7）。

我尝试进行自我连接和子查询，但我一定有心理障碍——我似乎无法正确处理。

提前致谢！

编辑

我忘了提到我正在寻找一个独立于数据库的查询。我在 SQlite 中对此进行了模拟，但很有可能我会在 DB2 或 Oracle 中实现它。我曾想过在我的查询中使用“limit 1”类型的运算符，但这在不同的数据库引擎之间是不同的。

使用 STLpriority_queue时，我一尝试使用pop(). 我可以将我的值推送到队列中，top()队列的值是我所期望和可访问的。pop()，当它去重新堆时，似乎有问题。

我在队列中存储指向模板类的指针。我有比较重载：

priority_queue是类的私有成员：

过载以它的方式工作，因为负距离被认为是无穷大，总是比其他任何东西都大；为了表示无穷大，距离被初始化为 -1。队列需要在顶部保持最小但非负数。

我取消引用重载中的指针，我在那里做什么是允许的吗？而且，我需要重载另一个运算符吗？

我会附上代码，但似乎如果我这样做，它会吓跑人们。请求查看更多，我将附加到另一条消息。

我动态声明了一个指向指针的指针数组，这些是被推送的，因为我假设priority_queue通过引用存储，所以如果我只是将循环中声明的指针放入队列中，该指针就会超出范围。这些指针指向正确的Vertex<type>，并且存在于整个函数中。

Visual Studio 2008 调试器将我带到“stdthrow.cpp”第 24 行。

我在 Unix 上的 C 中有一个排队机制。它接受 XML 事务。一些事务包含要存储的记录。其他事务请求这些事务。事务存储在一个文件中，该文件是一个本地队列。先进先出，非常简单。文件开头的标题区域，跟踪要读取的下一个位置和要写入的下一个位置。我们使用文件锁定，但不使用信号量，因为检索是从远程系统轮询的。并且只有一个程序可以访问队列。它在 C 中。多年来一直工作良好。

现在我们必须扩展系统。交易将包含一个额外的 XML 标记。我们必须根据该标签的值有选择地检索。我们将从一个简单的队列变成一个优先级队列。标签中可以有许多不同的值。说 AX、BX、CX、FL 和 TS。事务按接收顺序添加到队列中。我们需要能够按接收顺序检索它们，或者检索标签为 FL 的下一个事务。或 TS。或（CS 或 FL）。或者不是 AX。

如何最好地做到这一点？

简单快速是我们所需要的。我想到了几个选项：

1. 使用 Berkely DB 之类的东西将队列变成各种数据库。
2. 进入 PostgreSQL 数据库，创建一个可用作优先级队列的表。
3. 找到一个可以满足我们需求的 C 库。
4. 编写我们自己的基于磁盘的优先级队列。

我们有一些限制。时间在流逝，这需要在几周内完成。C 用于快速插入系统。如果我们能够以足够快的速度来转换访问队列的程序中的所有其他业务逻辑，那么可能是 Python。最好不要使用 PostgreSQL，因为我们无法控制数据库系统，而且 DBA 对他认为是“他的”的东西有不良习惯，即使这是一个关键系统，我们也没有正常运行时间的可靠性。政治啊！！DBA 还表示，使用 PostgreSQL 表并不是一种有效的方法。我们更喜欢本地化的东西，以便我们可以控制它。必须以闪电般的速度每分钟处理大量交易。

我对任何建议持开放态度，即使是遥远的建议。建议越多越好。

可能重复：
允许重复键的 C# 可排序集合

基本上，我想让 Dictionary 使用重复的键，而不需要进入自定义比较器实现。有一个想法：

但它仍然有一些开销。我希望字典有“AllowDuplicates”。

我需要一个始终保存n迄今为止插入的最大项目的数据结构（无特定顺序）。

所以，如果n是 3，我们可以在下面的会话中插入一些数字并且容器的内容发生变化：

你明白了。数据结构的名称是什么？实现这一点的最佳方法是什么？或者这是在某个图书馆？

我正在考虑使用一个容器，priority_queue它的元素（委托）使用反向比较，因此pop将删除最小的元素。因此该insert函数首先检查要插入的新元素是否大于最小元素。如果是这样，我们将最小的元素扔掉并推出新元素。

（我有一个C++实现，但问题与语言无关。）

Java 的优先级队列是一种数据结构，O(log n)对于 put（插入）和O(log n)poll（检索和删除 min 元素）具有复杂性。

C++ STL 的多重映射具有相同的功能，但O(1)在检索和删除最小元素（开始和擦除）方面很复杂。Java中是否有等价物？

我将使用 Java 中的线程池和优先级队列实现一个调度程序，我想问是否有人知道任何现有的实现，所以我没有花时间在它上面:-)...

基本上，java.util.concurrent 包中的 ScheduledThreadPoolExecutor 提供了我需要的几乎所有功能，除了“优先队列”。当我粗略检查了内置的 java 库时，我找不到任何支持在将元素放入队列后从外部修改和更新元素的“优先级”值的优先级队列。

我需要在喜欢下载者的项目中使用这种优先级队列。我想允许用户即时修改每个下载的优先级，并且它在队列中的位置会自动更新。PriorityQueue 不是以这种方式实现的，为了获得正确的优先级，每次我们更改其优先级值时，我们都必须将其删除并再次提交...

以前有人做过这个吗？