什麼時候優先在堆上使用單鏈表實現優先級隊列？

Question

我最近剛剛啓動了一個已經編寫了一些代碼的項目。我決定研究他的實現，發現他實現了一個帶有單鏈表的優先級隊列。

我對SLL的理解是，因爲您可能需要遍歷整個列表，所以實現它是低效的，這就是爲什麼堆首選的原因。但是，也許我錯過了某種背後的推理，並想知道是否有人曾經爲堆優先級隊列選擇過SLL的SLL？

Answer 1

There is SLL優於堆實現優先隊列的情況。例如：

1. 從隊列中移出需要儘可能快。從SLL移除O（1）（從列表/隊列的前面），同時從堆中移除O（log n）。我實際上遇到了這個問題，同時爲一個簡單的操作系統編寫了一個alarm()系統調用版本。我根本買不起O（log n）查找時間。與此相關的是，您需要一次刪除多個元素。從SLL中移除k個元素需要O（k）個時間，而需要O（k log n）個時間來處理堆。
2. 內存問題。最小或最大堆的傳統實現涉及一個數組，隨着堆的增長需要調整大小。如果你無法承擔大量的時間，那麼這個策略就不存在了。如果你將堆實現爲二叉樹，那麼你需要兩個指針而不是一個SLL。
3. 當你必須保持多個優先級。跟蹤不同鏈接列表中的相同節點是相對容易的。用堆做這件事情要複雜得多。

Answer 2

大學時我被告知我們使用鏈表的唯一原因是幫助我們理解指針。