優先級隊列的時間？

Question

• 優先列表需要多長時間才能構建n個節點列表？在上述時間它是如何完成的？

• delete-min函數（檢索最小元素並從列表中刪除它）需要多長時間？在上述時間它是如何完成的？

Answer 1

取決於你如何建立你的優先級隊列。如果您使用堆結構，則需要使用nlogn來構建優先隊列。我記得建立一個分鐘堆的方法也可以在O（N）中完成。查看CLRS瞭解更多信息。

查看堆結構以瞭解它如何構建堆結構。本質上你的比較器將是節點的優先級。

delete-min需要O（logn）。再看看堆數據結構。

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

您還可以使用優先級隊列鏈表。用鏈表，刪除min也是不變的。然而，根據您的輸入，構建優先級隊列可能會上升到O（N^2）。