高效的嵌套优先级队列
Efficient nested priority queue
我正在寻找一个 data-structure/algorithm（非多线程），它本质上是一个嵌套的优先级队列。即：
- 下一个要取的元素是优先级最高的元素。
- 一个元素可以是一个具有优先级的简单元素，也可以是另一个优先级队列（尽管对我的目的来说，嵌套一级的限制是可以的）。无论嵌套级别如何，queue/sub-queues/sub-sub-queues/etc 中优先级最高的元素是下一个选择的元素。
- 可以在任何级别添加或删除元素，但简单节点永远不会变成子队列（反之亦然）。
- 简单元素的优先级在插入后不会改变。
我什么都想不出来efficient/elegant，谷歌搜索也没找到任何东西。
我还没有实际构建它，但我对这个想法做了一些相当广泛的分析，它看起来应该可行。我称之为队列的队列。我从未构建它的原因是因为我正在构建它的项目在我需要队列之前被取消了。
首先，我决定 "simple element" 改为包含单个元素的优先级队列。不必管理两种不同类型的元素简化了设计，分析表明它不会对性能产生任何重大影响。
因为 sub-queue 的优先级可以在添加新项目或从中删除项目时发生变化，所以我选择对主队列和子队列使用 Pairing heap。当您必须进行大量优先级更改时，配对堆的性能优于二进制堆。二叉堆的问题是如果你想改变一个项目的优先级，你必须先找到这个项目。在二叉堆中，这是一个 O(n) 操作。在配对堆中，优先级更改的摊销成本为 O(log n)，因为您已经拥有对该节点的引用。
所以我们的想法是，如果您要添加一个新的 sub-queue，您只需将它添加到主队列中，它就会被放到正确的位置。如果你正在更新 sub-queue，你添加或删除项目（在 sub-queue 上是 O(log n)），然后调整 sub-queue 在主目录中的位置队列（在主队列上是 O(log n)）。
我所有的分析都表明这应该工作得很好，尽管我仍然不确定它在多线程下的工作情况。我 认为 我很清楚如何同步访问并且不会在每次插入和删除时阻塞整个队列，除了很短的时间。我想我会知道我是否会建造它。 可能可以创建一个lock-free并发配对堆。
我选择配对堆是因为它在 re-ordering 键中的性能更好，也因为它比 Fibonacci 堆或许多其他堆更容易实现，尽管它的渐近性能比 Fibonacci 堆慢，它的 real-world 性能要好得多。对我来说唯一的缺点是配对堆比等效的二进制堆占用更多的内存。这是旧的 time/space 权衡。
另一种选择是实现 skip list 优先级队列，它在插入和更改优先级方面也具有 O(log n) 性能。而且我已经看到 lock-free 并发跳过列表实现。在 C 中实现一个有效的跳过列表并不困难，因为它可以很好地处理可变记录大小。在 C# 和其他不允许构建可变长度结构的语言中，跳过列表可能是真正的内存消耗。
正如我所说，我从未真正构建过这个东西，但我所有的研究和设计笔记都告诉我它应该相当容易构建并且应该表现得很好。
我正在寻找一个 data-structure/algorithm（非多线程），它本质上是一个嵌套的优先级队列。即：
- 下一个要取的元素是优先级最高的元素。
- 一个元素可以是一个具有优先级的简单元素，也可以是另一个优先级队列（尽管对我的目的来说，嵌套一级的限制是可以的）。无论嵌套级别如何，queue/sub-queues/sub-sub-queues/etc 中优先级最高的元素是下一个选择的元素。
- 可以在任何级别添加或删除元素，但简单节点永远不会变成子队列（反之亦然）。
- 简单元素的优先级在插入后不会改变。
我什么都想不出来efficient/elegant，谷歌搜索也没找到任何东西。
我还没有实际构建它，但我对这个想法做了一些相当广泛的分析，它看起来应该可行。我称之为队列的队列。我从未构建它的原因是因为我正在构建它的项目在我需要队列之前被取消了。
首先，我决定 "simple element" 改为包含单个元素的优先级队列。不必管理两种不同类型的元素简化了设计，分析表明它不会对性能产生任何重大影响。
因为 sub-queue 的优先级可以在添加新项目或从中删除项目时发生变化，所以我选择对主队列和子队列使用 Pairing heap。当您必须进行大量优先级更改时，配对堆的性能优于二进制堆。二叉堆的问题是如果你想改变一个项目的优先级，你必须先找到这个项目。在二叉堆中，这是一个 O(n) 操作。在配对堆中，优先级更改的摊销成本为 O(log n)，因为您已经拥有对该节点的引用。
所以我们的想法是，如果您要添加一个新的 sub-queue，您只需将它添加到主队列中，它就会被放到正确的位置。如果你正在更新 sub-queue，你添加或删除项目（在 sub-queue 上是 O(log n)），然后调整 sub-queue 在主目录中的位置队列（在主队列上是 O(log n)）。
我所有的分析都表明这应该工作得很好，尽管我仍然不确定它在多线程下的工作情况。我 认为 我很清楚如何同步访问并且不会在每次插入和删除时阻塞整个队列，除了很短的时间。我想我会知道我是否会建造它。 可能可以创建一个lock-free并发配对堆。
我选择配对堆是因为它在 re-ordering 键中的性能更好，也因为它比 Fibonacci 堆或许多其他堆更容易实现，尽管它的渐近性能比 Fibonacci 堆慢，它的 real-world 性能要好得多。对我来说唯一的缺点是配对堆比等效的二进制堆占用更多的内存。这是旧的 time/space 权衡。
另一种选择是实现 skip list 优先级队列，它在插入和更改优先级方面也具有 O(log n) 性能。而且我已经看到 lock-free 并发跳过列表实现。在 C 中实现一个有效的跳过列表并不困难，因为它可以很好地处理可变记录大小。在 C# 和其他不允许构建可变长度结构的语言中，跳过列表可能是真正的内存消耗。
正如我所说，我从未真正构建过这个东西，但我所有的研究和设计笔记都告诉我它应该相当容易构建并且应该表现得很好。