堆或红黑树？

Question

我愿意使用数据结构作为常量空间的溢出缓冲区.我希望有效插入,但最重要的是有效去除min元素.我正在考虑使用堆,因为我有O(log(n))find_min()和log(n)插入和删除.另一方面,我知道不了解与红黑树相比的优势,因为它也有O(log(n))插入和删除但O(1)找到最小/最大.并排序输出的优势(我不关心).

问题与:红黑树是我理想的数据结构吗？

由于我从std :: map和boost :: heap可以获得这两个结构,为什么我更喜欢使用堆而不是红黑树呢？最后,使用红黑树我也有一个条目的O(log(n))搜索时间,而对于一个堆,时间是O(n),这是重要的,因为存在重复.

Answer 1

不同之处主要在于如何使用这些结构.

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

• 红/黑树是平衡的二叉搜索树,支持有效插入,删除,查找任意值,以及(相当快)查找最小值.但是,与二进制堆相比,它们有很多开销.

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

另请注意,std::priority_queue如果需要二进制堆,则可以使用; 你不需要使用Boost.它也不能保证std::map是红/黑树; 它可能是某种平衡的BST,但可以使用其他算法进行平衡.

希望这可以帮助!

Answer 2

堆很容易在连续内存（即数组）中实现。红黑树通常是通过为每个节点分配单独的堆来构建的。红黑树最终会在每次树遍历时访问整个堆上的内存。这是最坏情况的缓存行为。尽管两种结构的某些操作的算法复杂性相同，但红黑树的恒定开销要高得多。