堆还是红黑树？

Question

我愿意使用数据结构作为常量空间的溢出缓冲区。我希望有有效的插入，但最重要的是高效删除min元素。我考虑使用堆，因为我有O( log(n) )、find_min()和log(N)插入和删除。另一方面，我知道与红黑树相比，我不理解它的优势，因为它还有O(log(n))、insert和delete，以及O(1)查找min/max。以及排序输出的优点(我不关心这个)。

这个问题与：Is a red-black tree my ideal data structure?有关

既然我有std::map和boost：：堆这两种结构，为什么我更喜欢使用堆而不是红黑树呢？最后，使用红黑树，我还有O(log(n))搜索条目的时间，而堆的搜索时间是O(n)，这一点很重要，因为存在重复。

Answer 1

区别主要在于你将如何使用这些结构。

• 二进制堆是用于插入值和检索最小值的非常快速的数据结构。但是，它们不支持有效地搜索或删除随机值。
• 红色/黑色树是平衡的二进制搜索树，支持有效的插入、删除、任意值的查找和(合理快速)查找-最小值。但是，与二进制堆相比，它们有很大的开销。

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

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

希望这能有所帮助！

Answer 2

堆很容易在连续内存(即数组)中实现。通常为每个节点使用单独的堆分配来构造红黑树。红黑树在每次遍历树时都会访问堆中的所有内存。这是最坏的缓存行为。尽管对于这两种结构，某些运算的算法复杂度是相同的，但是红黑树的恒定开销要高得多。