c++ - 堆还是红黑树？

我愿意将数据结构用作恒定空间的溢出缓冲区。我想有效插入，但最重要的是要有效去除min元素。我正在考虑使用堆，因为我有O(log(n))find_min()和log(n)插入和删除。另一方面，我知道不了解与红黑树相比的优势，因为它也具有O(log(n))插入和删除功能，而O(1)可以找到最小值/最大值。排序输出的优点(我不在乎)。

问题与:Is a red-black tree my ideal data structure?

由于我从std::map和boost::heap中都有可用的两种结构，为什么我应该更喜欢使用堆而不是红黑树？
最后，使用红黑树，我还具有O(log(n))搜索条目的时间，而对于堆，时间是O(n)，这很重要，因为存在重复项。

最佳答案

区别主要在于如何使用结构。

二进制堆是用于插入值和检索最小值的非常快速的数据结构。但是，它们不支持有效搜索或删除随机值。

红色/黑色树是平衡的二进制搜索树，它们支持有效的插入，删除，查找任意值和(合理地快速)最小查找。但是，与二进制堆相比，它们有很多开销。

如果您只需要插入，最小查找和最小删除，则二进制堆可能是一个更好的选择，因为开销较低，运行时应该更快。如果您需要插入和删除任意值或查找任意值，则红色/黑色树可能是更好的选择。与所有工程一样，选择正确的数据结构只需要权衡。

另外，请注意，如果需要二进制堆，则可以使用std::priority_queue。您不需要使用Boost。也不能保证std::map是一棵红/黑树；它可能是某种平衡的BST，但可以使用其他算法来平衡它。

希望这可以帮助!