的OCaml的參考手冊提供了優先級佇列實作的示例。
它是基于圖的堆實作。我說“堆”是因為每個節點都有 0、1 或 2 個子節點，并且父節點小于或等于其子節點。然而，它不是一個“二元堆”，因為插入演算法不會強制葉子最左對齊（根據維基百科的定義應該是這樣），所以樹并不完整。
我的直覺是樹是平衡的，因為每次我們插入一個新節點時：左子樹移動到右子樹，前一個右子樹添加節點并成為新的左子樹。下面的插入會將之前稱為“新右子樹”的位置向左移動并添加節點。
所以左子樹的深度與右子樹的深度之差永遠不會超過 1，所以樹是平衡的。因此，我們永遠不應該以具有鏈表形式的樹結束，并且最壞情況的復雜性應該保持 O(log n) - 而插入演算法更簡單，因為它不負責保持樹的完整性（但僅均衡）。
我的直覺在這里正確嗎？我做了一些研究，并沒有在其他地方找到這個演算法（相反，大多數演算法都專注于基于陣列的實作，這顯然需要一個完整的樹，否則某些插槽可能是“無效的”）。
謝謝
uj5u.com熱心網友回復：
您對堆在插入程序中保持平衡的方式是正確的。
然而，removeMin 操作可能會擾亂平衡，因為例如，所有左邊的元素都可能低于右邊的所有元素。沒有什么可以恢復平衡，因此可能會失去平衡。
所以這個堆不提供任何 O(log N) 保證，如果 N 是堆的大小。但是，如果 N 是插入的總數，它確實如此，這還不錯。它不會損害大多數使用堆的演算法的復雜性。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/353919.html
下一篇：在C 中的文本字串中的模式搜索