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

Question

我们知道堆和红黑树都具有以下特性:

搜索的最坏情况成本是 lgN；

插入的最坏情况成本是 lgN。

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

Answer 1

您无法在 O(log n) 的堆中找到任意元素。需要 O(n) 来做到这一点。您可以在 O(1) 的堆中找到第一个元素(比如最小的)，并在 O(log n) 中提取它。红黑树和堆具有完全不同的用途、内部顺序和实现:有关更多详细信息，请参见下文。

典型用途

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

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

结构 强加的一致性约束

红黑树:总排序:左 child < parent <右 child 。

堆:优势:仅父<子。

(请注意，您可以替换比 < 更通用的排序)

实现/内存开销

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

堆:结构是隐式的:根在位置 0，根的 child 在 1 和 2 等，所以每个元素没有开销。通常只存储在单个数组中。