优先级经常变化的作业优先级队列的数据结构
Data structure for a priority queue of jobs with priority that changes often
我有一个工人class，我可以向工人提交工作。 Worker 保留这些作业并按优先级顺序依次运行它们（优先级基本上可以是任何 unsigned int）。对于这种情况，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 似乎是一个更好的选择：优先级更改或 update/removal 是 O(1)，当我需要删除作业时，它是 O(N) 来遍历整个列表以找到应该的最高优先级项目发生频率低于修改优先级。
另一个观察结果表明，尽管工作优先级经常变化，但这些变化并不一定会导致顺序变化，例如我可以简单地更新我的集合的关键元素（通过放弃常量或使关键可变？）如果该更改仍会使修改后的元素保持在左右节点之间。对于这样的优先队列，你有什么建议？任何boost容器或自定义数据结构设计都可以。
在 set/map 的情况下，我使用优先级作为键。为了使键在我的例子中唯一，每个键实际上是两个整数：作业序列号（从我为每个新请求递增的 atomic int 派生）和实际优先级数。这样，如果我添加多个具有相同优先级的作业，它们将按计划的顺序执行，因为序列号会使它们保持有序。
基本上您正在寻找 IndexPriorityQueue。您可以根据需要实现自己的索引优先级队列变体。
索引优先级队列允许您降低键值或增加键值，即基本上您可以提高或降低作业的优先级。
以下是javaIndexMinQueue的实现，希望对您有所帮助。 IndexMinQueue
一个简单的优先级堆应该符合您的要求。插入、删除和优先级更改都是 O(log n)。但是你说通常优先级的改变不会导致顺序的改变。因此，在优先级堆的情况下，当您更改优先级时，您将针对父级和 2 个子级检查更改的项目，如果违反堆条件的 none，则不需要向上或向下堆操作。所以很少需要完整的 O(log n) 时间。实际上它会更像 O(1).
现在为了高效操作，给定一个项目 I 您可以在 O(1) 中找到该项目在堆中的位置并访问父项和子项是至关重要的。
如果堆只包含数组中的项目，那么这只是指针算法。缺点是重新排序堆意味着复制项目。
如果您在堆中存储指向项目的指针，那么您还必须在项目自身中存储对堆中位置的反向引用。当您重新排序堆时，您只需要交换指针并更新反向引用。
我有一个工人class，我可以向工人提交工作。 Worker 保留这些作业并按优先级顺序依次运行它们（优先级基本上可以是任何 unsigned int）。对于这种情况，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 似乎是一个更好的选择：优先级更改或 update/removal 是 O(1)，当我需要删除作业时，它是 O(N) 来遍历整个列表以找到应该的最高优先级项目发生频率低于修改优先级。
另一个观察结果表明，尽管工作优先级经常变化，但这些变化并不一定会导致顺序变化，例如我可以简单地更新我的集合的关键元素（通过放弃常量或使关键可变？）如果该更改仍会使修改后的元素保持在左右节点之间。对于这样的优先队列，你有什么建议？任何boost容器或自定义数据结构设计都可以。
在 set/map 的情况下，我使用优先级作为键。为了使键在我的例子中唯一，每个键实际上是两个整数：作业序列号（从我为每个新请求递增的 atomic int 派生）和实际优先级数。这样，如果我添加多个具有相同优先级的作业，它们将按计划的顺序执行，因为序列号会使它们保持有序。
基本上您正在寻找 IndexPriorityQueue。您可以根据需要实现自己的索引优先级队列变体。
索引优先级队列允许您降低键值或增加键值，即基本上您可以提高或降低作业的优先级。
以下是javaIndexMinQueue的实现，希望对您有所帮助。 IndexMinQueue
一个简单的优先级堆应该符合您的要求。插入、删除和优先级更改都是 O(log n)。但是你说通常优先级的改变不会导致顺序的改变。因此，在优先级堆的情况下，当您更改优先级时，您将针对父级和 2 个子级检查更改的项目，如果违反堆条件的 none，则不需要向上或向下堆操作。所以很少需要完整的 O(log n) 时间。实际上它会更像 O(1).
现在为了高效操作，给定一个项目 I 您可以在 O(1) 中找到该项目在堆中的位置并访问父项和子项是至关重要的。
如果堆只包含数组中的项目，那么这只是指针算法。缺点是重新排序堆意味着复制项目。
如果您在堆中存储指向项目的指针，那么您还必须在项目自身中存储对堆中位置的反向引用。当您重新排序堆时，您只需要交换指针并更新反向引用。