为什么使用堆而不是红黑树？

Question

显然，红黑树相对于堆的优点是可以支持O(logn)的删除操作，而堆需要 O(n) 的时间。

然而，似乎所有红黑树的操作都比堆更快/相等。所以我的问题是，为什么我们会使用堆而不是红黑树？在我看来，红黑树可以做任何堆能做的事情，但更快/相等。

谢谢。

- Wonjoo Lee

---

这个问题基本上与编程无关，请在 https://cs.stackexchange.com/ 上提问，该网站主要设计用于解决类似您的问题。 - Adnan Ahmad Khan

为什么是O(n)？当你移除根节点时（这也许是使用该数据结构的原因），它就变成了O(log n)。至于好处，节点之间的链接不是必需的，所以你可以在原地进行堆化和排序数组。 - Alexey Frunze

可能是堆与二叉搜索树（BST）的重复问题。 - Bernhard Barker

谢谢你提出这个问题，我在stackoverflow上找到了它，然后在cs questions上看到了答案。如果你没有在这里提问，我就永远不会发现它。 - Noitidart

Answer 1

使用最小堆的一个主要用例是优先队列，其中主要操作为push（newval），pop_smallest（），inspect_smallest()。

在这种情况下，堆赢了，因为inspect_smallest()搜索步骤是O(1)。最小值始终位于位置零。

此外，虽然红黑树和最小堆的插入和删除时间都是O(log n)，但最小堆的常数因子更小。

此外，堆可以比红黑树更紧凑地表示。不需要“着色”位，树本身可以轻松表示为数组，因此无需存储指针。

简而言之，如果应用程序不需要一般搜索，而是可以专注于最低值，则堆提供了一种更简单，更便宜的替代方案。

- Raymond Hettinger