堆或紅黑樹？

我願意使用數據結構作爲恆定空間的溢出緩衝區。我想有效插入，但最重要的是有效去除最小元素。因爲我有O（log（n））find_min（）和log（n）插入和刪除，所以我正在考慮使用堆。另一方面，我知道不理解與紅黑樹相比的優點，因爲它也有O（log（n））插入和刪除，而O（1）找到最小/最大。和排序輸出的優點（我不在乎）。堆或紅黑樹？

的問題是關於：Is a red-black tree my ideal data structure?

既然我都可以從性病::地圖和自boost ::堆結構的我爲什麼要喜歡使用堆，而不是紅黑樹的？最後，使用紅黑樹我也有一個入口O（log（n））搜索時間，而堆的時間是O（n），這是重要的，因爲重複存在。

來源

2013-07-17 nikosdi

考慮環形緩衝區。不知道它是否適合您的使用。 –

[堆與二進制搜索樹（BST）]的可能重複（http://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst） –

區別主要在於如何使用結構。

二進制堆是非常快速的數據結構，用於插入值和檢索最小值。但是，它們不支持高效搜索或刪除隨機值。
紅色/黑色樹是平衡二叉搜索樹，支持有效插入，刪除，查找任意值和（相當快）查找最小值。但是，與二進制堆相比，它們有很多開銷。

如果你需要的是插入，找到最小，並刪除最小，二進制堆可能是一個優越的選擇，因爲開銷較低，運行時間應該會更快。如果您需要插入和刪除任意值或查找任意值，則紅/黑樹可能是更好的選擇。與所有工程一樣，選擇正確的數據結構完全取決於折衷。

另外，請注意，如果您需要二進制堆，則可以使用std::priority_queue;你不需要使用Boost。也不能保證std::map是紅/黑樹;它可能是某種平衡的BST，但可以使用其他算法進行平衡。

希望這會有所幫助！

來源

2013-07-17 19:28:06 templatetypedef

感謝您的快速回答。在我的數據中，我有重複的，所以我不能避免find（），這在堆上很貴。另一方面，插入和擦除在堆中更快，但在紅黑樹中是對數的。我猜紅黑樹是這個問題的正確答案。但是，即使他們有find（）操作，我也在一篇論文中看到過，這就是爲什麼我很困惑。 – nikosdi

堆不是搜索數據結構;但是，您可以將元素的位置存儲在堆中，因此稍後您可以更改其優先級（這會相應地將元素向上或向下移動）。許多基於掃描線的幾何算法需要這種「查找和更新」。 – DanielKO

堆很容易在連續內存中實現，即數組。紅黑樹通常是爲每個節點構建一個單獨的堆分配。紅黑樹最終訪問遍歷每個樹遍歷的內存。這是最糟糕的緩存行爲。儘管兩種結構的某些操作的算法複雜性相同，但紅黑樹的持續開銷要高得多。

來源

2013-07-17 20:04:15 japreiss

堆或紅黑樹？

回答

相關問題