二進制堆的所有目的

定義：

甲優先級隊列是一個抽象數據類型，是像一個普通的隊列或堆棧數據結構，但其中另外的每個元素具有「優先級」與它相關聯。在優先級隊列中，具有高優先級的元素在低優先級的元素之前被服務。如果兩個元素具有相同的優先級，則它們將根據其在隊列中的順序進行服務。二進制堆的所有目的

實現：

爲了實現優先級隊列，無序陣列，排序後的數組和二進制堆數據結構是3個實施策略。

具體而言，二進制堆實現策略可使用數組鍵的，

或

每個鍵如二進制節點來表示具有兩個孩子。

問：

除了優先級隊列的實現，都是自己用二進制堆數據結構的任何其他應用程序？

來源

2017-01-04 overexchange

另請參見堆排序。 –

不是。甚至可能會爭辯說，只是填充一個優先級隊列，然後將事情排除在外。二進制堆*是一個優先級隊列。更重要的問題是什麼是優先級隊列的應用程序，哪些最好用二進制堆實現，哪些應該使用其他優先級隊列實現。 –

1.請提供您從中複製的來源的正確歸屬。請參閱http://stackoverflow.com/help/referencing。 2.要求提供二進制堆的所有應用程序列表可能過於寬泛。 3.你做了什麼研究？你看過數據結構教科書，看看他們用堆做什麼？ –

二進制堆可用於提取O（logn）時間內的（max或min）元素。該屬性可用於許多算法中以獲得更好的運行時間。

例如，我曾將它用於k合併排序算法中，以增加k合併排序的排序步驟的時間效率。簡而言之，它構成了k-子陣列的二進制堆，並且可以在線性時間內完成排序，這比合並排序的通常排序步驟更好。

它也用於Dijkstra算法，Prim算法來減少它們的運行時間。

您還可以看看here

來源

2017-01-04 09:58:27 CODError

您無法在二進制堆中以恆定時間提取元素。 * delete-min *是一個O（log n）操作。另外，OP要求使用二進制堆而不是實現優先級隊列。您的三個示例（合併排序，Dijkstra算法，Prim算法）均基於優先級隊列。二進制堆只是一個方便的實現。 –

我更正了我的答案。感謝您指出。我正在嘗試列舉二進制堆的少量用法。我沒有談論實施。如果您在不使用二進制堆作爲優先級隊列時遇到任何情況，則歡迎您發表評論。我會很高興學習。 – CODError

「提取（最大或最小）元素」 - 這實際上是優先級隊列的定義，因此您沒有回答這個問題，正如@JimMischel指出的那樣。 \t 「如果你有任何情況，當你不使用二進制堆作爲優先級隊列」 - 你有它倒退。有幾種方法可以在不使用堆的情況下實現優先級隊列...... OP提到了排序和未排序的數組，還有許多其他的方法。問題是二進制堆是否適合其他任何事情。看到我的答案...是一個實際的答案。編輯：我想也許你沒有倒退，只是表達不好。 –

二進制堆有一個其他有用的（和主要的）應用程序：堆排序。 HeapSort的開銷比QuickSort高，但最壞的情況是O（n log n）與QuickSort的O（n * n）。一旦間隔足夠短，可以通過切換到HeapSort來改進QuickSort，以獲得最差的O（n log n） - 這被稱爲IntroSort，並且是STL和C++標準庫中使用的。請參閱https://en.wikipedia.org/wiki/Introsort

來源

2017-01-05 08:42:33

二進制堆的所有目的

定義：

實現：

回答

相關問題