有效嵌套优先级队列

Question

我正在寻找一个数据结构/算法(而不是多线程)，它本质上是一个嵌套的优先级队列。这就是：

1. 下一个要考虑的因素是最优先考虑的因素。
2. 一个元素可以是一个具有优先级的简单元素，也可以是另一个优先级队列(尽管对一个层次嵌套的限制对我来说是可以的)。不管嵌套级别如何，跨队列/子队列/子队列/etc的优先级最高的元素是选中的nexxt。
3. 元素可以在任何级别上添加或删除，尽管简单的节点永远不会变成子队列(反之亦然)。
4. 简单元素的优先级在插入后不会改变。

我还没有想出任何有效率/优雅的东西，谷歌也没有发现任何东西。

Answer 1

我还没有真正建立这个，但是我对这个想法做了一些非常广泛的分析，看起来它应该是可行的。我把它叫做排队。我从未构建它的原因是因为我构建它的项目在我需要队列之前就被取消了。

首先，我决定将“简单元素”改为包含单个元素的优先级队列。不需要管理两种不同类型的元素，就简化了设计，并且分析表明，它不应该以任何重要的方式影响性能。

由于子队列的优先级可能在添加新项或从其中移除项时发生更改，所以我选择对主队列和子队列使用配对堆。当您需要做很多优先级更改时，配对堆比二进制堆表现得更好。二进制堆的问题是，如果要更改项的优先级，必须先找到项。在二进制堆中，这是一个O(n)操作。在配对堆中，优先级更改的摊还成本是O(log )，因为您已经有了对节点的引用。

因此，如果您要添加一个新的子队列，只需将其添加到主队列中，它就会被放在适当的位置。如果要更新子队列，则添加或移除子队列中的项(子队列上为O(log ))，然后调整子队列在主队列中的位置(即主队列上的O(log ))。

我所有的分析都说这应该工作得很好，尽管我仍然不确定它在多个线程中的工作效果如何。我想我很清楚如何同步访问，并且除了很短的时间外，不会在每次插入和删除时阻塞整个队列。我想我会找出我是否建造过它。可以创建一个无锁的并发配对堆。

我之所以选择配对堆，是因为它在重排序键方面的性能更好，也因为它比斐波纳契堆或许多其他堆更容易实现，尽管它的渐近性能比斐波纳契堆慢，但它的实际性能要好得多。对我来说，唯一的缺点是配对堆比等效的二进制堆占用更多的内存。这是旧的时间/空间的权衡。

另一个选项是实现一个跳过列表优先级队列，该队列具有O(log )的插入和更改优先级的性能。我也见过无锁并发跳过列表实现。在C中实现高效的跳过列表并不困难，因为它很好地处理了可变记录大小。在C#和其他不允许构建不同长度结构的语言中，跳过列表可能是真正的内存占用。

就像我说的，我从来没有真正建造过这个东西，但是我所有的研究和设计说明都告诉我，它应该是相当容易建造的，并且应该表现得相当好。