什么时候最好使用单链表而不是堆来实现优先级队列？
我最近刚刚启动了一个项目，其中一些代码已经编写完毕。我决定研究他的实现，发现他实现了带有单链表的优先级队列。
我对 SLL 的理解是，由于您可能必须迭代整个列表，因此实现它的效率很低，这就是为什么堆是首选的原因。然而，也许我缺少其背后的某种推理，并且想知道是否有人选择过 SLL 而不是堆作为优先级队列？
I recently just started up a project with some code that has been already written. I decided to look into his implementation and found that he implemented a Priority Queue with a Singly Linked List.
My understanding of SLLs is that since you may have to iterate over the entire list, it's inefficient to implement it as such, which is why Heaps are preferred. However, perhaps I am missing some sort of reasoning behind it and was wondering if anyone has ever chosen an SLL over a Heap for a Priority Queue?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
在某些情况下，SLL 比堆更适合实现优先级队列。例如：
realloc所需的时间，那么此策略就不再适用。如果将堆实现为一棵二叉树，则需要两个指针，而不是 SLL 的一个指针。There are situations where a SLL is better than a heap for implementing a priority queue. For example:
alarm()syscall for a simple OS. I simply could not afford the O(log n) lookup time. Related to this is when you need to remove multiple elements at a time. Removing k elements from an SLL takes O(k) time while it takes O(k log n) time for a heap.reallocthen this strategy is out. If you implement the heap as a binary tree, then you need two pointers instead of one for an SLL.在大学里，有人告诉我，我们使用链表的唯一原因是帮助我们理解指针。
In college I was told that the only reason we were made to use Linked Lists was to help us with our understanding of pointers.