Dijkstra的D-Ary堆算法的大O

Question

我正在尋找一個完整的Dijkstra算法的運行時演練，當用D-Ary堆實現時。

我現在最好的理解是樹的深度至多是log_d（n），所以插入和冒泡的最大時間是log_d（n）。在刪除一個節點時不會冒泡？

我只是無法將事物拼湊在一起，在這裏找到總的Big-O運行時。我的理解是它應該是O（m logm/n n）），但我希望有一種演練來理解爲什麼會這樣。

Answer 1

在d-ary堆中，上堆（例如，插入，如果跟蹤堆節點移動時減少鍵）需要時間O（log_d n）和下堆（例如，刪除最小值）花費時間O（d log_d n），其中n是節點的數量。下堆更昂貴的原因是我們必須找到最小的孩子來提升，而上堆只是與父母比較。假設連接圖，Dijkstra最多使用m - （n - 1）個減少鍵，最多使用n - 1個插入/刪除（假設我們從不插入根）。 Dijkstra使用d-ary堆作爲優先級隊列的運行時間因此是O（（m + n d）log_d n），這對於密集圖是值得的。