我最近刚刚启动了一个项目，其中包含一些已经编写好的代码。我决定研究他的实现，发现他实现了一个带有单向链表的优先级队列。
我对 SLL 的理解是，由于您可能必须遍历整个列表，因此这样实现它效率低下，这就是首选堆的原因。但是，也许我错过了它背后的某种推理，并且想知道是否有人为优先级队列选择了 SLL 而不是堆？
最佳答案
在 情况下，SLL 比堆更适合实现优先级队列。例如:
- 当需要尽快从队列中移除时。从 SLL 中删除是 O(1)(从列表/队列的前面开始)，而从堆中删除是 O(log n)。实际上，我在为一个简单的操作系统编写一个版本的
alarm()系统调用时遇到了这个问题。我根本负担不起 O(log n) 查找时间。与此相关的是您需要一次删除多个元素。从 SLL 中删除 k 个元素需要 O(k) 时间，而从堆中删除需要 O(k log n) 时间。 - 内存问题。最小或最大堆的传统实现涉及一个数组，需要随着堆的增长调整其大小。如果您负担不起执行大型
realloc所花费的时间，那么该策略就被淘汰了。如果将堆实现为二叉树，则需要两个指针而不是 SLL 的一个指针。 - 当您必须维护多个优先级时。跟踪不同链表中的相同节点相对容易。使用堆执行此操作要复杂得多。
关于c - 什么时候用堆上的单链表实现优先级队列比较好？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6414622/