堆和红黑树之间有什么区别？

Question

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

用于搜索

1. 最坏情况下的成本是LGN;
2. 插入的最坏情况成本为lgN。

因此，由于红黑树的实施和运行很困难，为什么我们不使用堆而不是红黑树呢？我很困惑。

Answer 1

红黑树：
具有确定性平衡策略的二叉搜索树的形式。这种平衡保证了良好的性能，并且始终可以在O（log n）时间内进行搜索。

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

Answer 2

首先，这不是一个stackoverflow问题，因为维基百科对于这个问题已经足够了。 （在提问前阅读常见问题解答）

其次，由于没有能够在堆中搜索O（log n）的算法，因此您的困惑更加深入。

堆和红黑树在完全不同的场景中使用。

RBT通常用于维持高度平衡的BST，以将其中的各种操作限制在log n的顺序。堆通常用于执行优先级队列。

Answer 3

在O(log n)中，您无法在堆中找到任意元素。这需要O(n)。你可以在O(1)和提取找到第一个元素（最小的，比如说），它位于O(log n)。红黑树和堆有非常不同的用途，内部排序和实现：请参阅下面的更多详细信息。

典型用途

红黑树：存储字典哪里以及查找你想要排序的关键元素，让你可以例如为了遍历它们。插入和查找是O(log n)。

堆：优先队列（和堆排序）。最小和插入的提取是O(log n)。通过结构强加

红黑树

一致性约束：全序：左子<父母<右子。

堆：支配地位：家长<仅限儿童。

（请注意，您可以替换更一般的订货比<）

执行/内存开销

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

堆：结构是隐含的：根在位置0，在1和2等根的孩子，所以没有每个元素的开销。通常只存储在一个数组中。