data-structures - 堆和红黑树有什么区别？

Question

我们知道堆和红黑树都具有以下属性：

1. 搜索的最坏情况成本是 lgN；
2. 插入的最坏情况成本是 lgN。

那么，既然红黑树的实现和操作比较困难，为什么不直接用堆代替红黑树呢？我很困惑。

Answer 1

您无法在O(log n). 需O(n)要这样做。您可以在堆中找到第一个元素（例如最小的）O(1)并将其提取到O(log n). 红黑树和堆有完全不同的用途、内部排序和实现：更多细节见下文。

典型用途

红黑树：将字典存储在哪里以及查找您希望按键排序的元素，以便您可以按顺序遍历它们。插入和查找是O(log n).

堆：优先队列（和堆排序）。提取最小值和插入是O(log n)。

结构施加的一致性约束

红黑树：总排序：左孩子<父母<右孩子。

堆：优势：仅父<子。

（请注意，您可以替换为比 < 更一般的排序）

实现/内存开销

红黑树：用于表示树结构的指针，因此每个元素的开销。通常使用在免费存储上分配的多个节点（例如new在 C++ 中使用），节点指向其他节点。保持平衡以确保对数查找/插入。

堆：结构是隐式的：根位于位置 0，根的子级位于 1 和 2，依此类推，因此每个元素没有开销。通常只存储在单个数组中。

Answer 2

红黑树：
具有确定性平衡策略的二叉搜索树的形式。这种平衡保证了良好的性能，并且总是可以在 O(log n) 时间内搜索到。

堆：
我们需要搜索堆中的每个元素以确定元素是否在里面。即使进行了优化，我相信搜索仍然是 O(N)。另一方面，最好在 O(1) 集合中找到最小值/最大值。