c++ - 具有经常更改优先级的作业的优先级队列的数据结构
问题描述
我有一个工人阶级，我可以向工人提交工作。Worker 保留这些作业并按优先级顺序运行它们（优先级基本上可以是任何无符号整数）。对于这种情况，可以使用 std::priority_queue 甚至 std::set/map 来存储按优先级排序的作业，然后工作人员将能够在 O(1) 中按顺序提取它们。添加工作将是 O(log N)。
现在，我的要求是能够更改任何已提交作业的优先级。在 std::set/map 的情况下，我需要删除并重新添加具有不同优先级的作业。这将是 O(log N) 并且除此之外，使用 set/map 它将在内部重新分配节点 afaik （尽管这可能会在 C++17 中避免）。不同寻常的是，在我的情况下，我会更频繁地更新作业优先级，而不是安排或执行它们。基本上我可能会安排一次工作，在它执行之前，我可能最终会更新它的优先级数千次。事实上，每项工作的优先级每秒都会改变 10-20 次。就我而言，假设我的队列中不会有超过 10K 的作业是相当安全的。在我的流程开始时，我希望它总是增长到 10K 左右的作业，并且随着这些作业被删除，队列最终应该一直几乎是空的，偶尔会添加 10-50 个新作业，但它不应该增长超过1000个工作岗位。工作将以每秒几个工作的速度被删除。由于我对频繁优先级更新 std::priority_queue 或集合的奇怪要求似乎不太合适。普通的 std::list 似乎是一个更好的选择：优先级更改或更新/删除是 O(1)，当我需要删除作业时，它是 O(N) 遍历整个列表以找到应该不那么频繁发生的最高优先级项目而不是修改优先级。工作将以每秒几个工作的速度被删除。由于我对频繁优先级更新 std::priority_queue 或集合的奇怪要求似乎不太合适。普通的 std::list 似乎是一个更好的选择：优先级更改或更新/删除是 O(1)，当我需要删除作业时，它是 O(N) 遍历整个列表以找到应该不那么频繁发生的最高优先级项目而不是修改优先级。工作将以每秒几个工作的速度被删除。由于我对频繁优先级更新 std::priority_queue 或集合的奇怪要求似乎不太合适。普通的 std::list 似乎是一个更好的选择：优先级更改或更新/删除是 O(1)，当我需要删除作业时，它是 O(N) 遍历整个列表以找到应该不那么频繁发生的最高优先级项目而不是修改优先级。
另一个观察结果是，即使工作优先级经常变化，这些变化也不一定会导致顺序变化，例如，我可以简单地更新我的集合的关键元素（通过抛弃 constness 或使 key 可变？）如果这种变化仍然保持不变左右节点之间的修改元素。你对这样的优先队列有什么建议？任何 boost 容器或自定义数据结构设计都可以。
在设置/映射的情况下，我使用优先级作为键。在我的情况下，为了使键唯一，每个键实际上是两个整数：作业序列号（从原子 int 派生，我为每个新请求递增）和实际优先级编号。这样，如果我添加多个具有相同优先级的作业，它们将按计划的顺序执行，因为序列号将使它们保持有序。
解决方案
基本上你正在寻找一个 IndexPriorityQueue。您可以根据需要实现自己的索引优先级队列变体。
索引优先级队列允许您减少或增加 key ，即基本上您可以增加和减少作业的优先级。
下面是IndexMinQueue的java实现，希望对你有所帮助。索引最小队列