CHDataStructures:优先级队列？

Question

我需要一个优先级队列，我猜在框架中，CHMutableArrayHeap和CHBinaryHeap可以完成这项工作，对吧？

但是，如果我将具有相同优先级的对象发送到队列，则CHMutableArrayHeap和CHBinaryHeap都无法保持它们的添加顺序。

例如，我有从obj1到obj10的对象，它们的优先级是相同的。当我将这10个对象从1到10逐个添加到队列中后，它们的位置与添加顺序不同，obj4可能会排在obj1之前。

那么，Quinn，如果我想要一个优先级队列，如果优先级是相同的，保持添加顺序，你有什么建议？

谢谢

Answer 1

(对不起，我几乎看不到这个问题。)

堆的本质是它根本不保留插入顺序，因此您必须(1)在另一个数据结构之上构建一个优先级队列，或者(2)用另一个跟踪插入顺序的数据结构来补充堆。但是，堆通常是实现优先级队列的最有效(也是首选)的方法，所以我不知道使用其他方法是否是个好主意。我这么说的主要原因是，您希望插入非常快，这是堆提供的；添加到排序数组则不能。

一种可能性是为每个优先级维护一个队列(例如CHCircularBufferQueue)。(我想您会想要创建一个管理队列的包装器结构，这样调用者就不必直接处理它们了。)您可以将队列存储在以包含优先级的NSNumber为关键字的字典中，但我不知道性能会是什么样子。这显然不能非常有效地扩展到非常广泛的优先级范围，并且可能不适用于大量的插入和删除，但在小型情况下可能是可行的。这只是个想法。

另一个想法是创建一个同时存储优先级和插入时间的包装类，然后按顺序比较它们。在这种情况下，您可能希望使用排序集(例如二叉树)来存储它们。但是，额外的开销意味着您不会获得与堆相同的性能，但我认为这是保持插入顺序的权衡。

更新：我发现了以下相关问题：

• How to preserve the order of elements of the same priority in a priority queue implemented as binary heap?
• Priority Queue C
• Priority queue implementation in C
• priority queue data structure
• Implementing Java Priority Queue
• https://cstheory.stackexchange.com/questions/593/is-there-a-stable-heap

https://stackoverflow.com/questions/tagged/priority-queue