c - 什么时候最好在堆上使用单链表来实现优先级队列？

Question

我最近刚刚启动了一个项目，其中包含一些已经编写的代码。我决定研究他的实现，发现他实现了一个带有单链表的优先级队列。

我对 SLL 的理解是，由于您可能必须遍历整个列表，因此实现它的效率很低，这就是首选堆的原因。但是，也许我错过了它背后的某种推理，并且想知道是否有人曾经为优先队列选择 SLL 而不是堆？

Answer 1

在某些情况下，SLL 比堆更适合实现优先级队列。例如：

1. 从队列中移除时需要尽可能快。从 SLL 中删除是 O(1)（从列表/队列的前面），而从堆中删除是 O(log n)。alarm()实际上，我在为一个简单的操作系统编写系统调用版本时遇到了这个问题。我根本负担不起 O(log n) 查找时间。与此相关的是当您需要一次删除多个元素时。从 SLL 中删除 k 个元素需要 O(k) 时间，而堆需要 O(k log n) 时间。
2. 内存问题。最小或最大堆的传统实现涉及一个数组，需要随着堆的增长而调整其大小。如果你负担不起做大的时间，realloc那么这个策略就失效了。如果将堆实现为二叉树，则 SLL 需要两个指针而不是一个。
3. 当您必须维护多个优先级时。跟踪不同链表中的相同节点相对容易。用堆做这件事要复杂得多。

Answer 2

在大学里，有人告诉我，我们使用链表的唯一原因是帮助我们理解指针。