data-structures - 为什么在红黑树上使用堆？

Question

明显的区别在于，与堆的 O(n) 移除相比，红黑树可以支持 O(logn) 移除。

但是，看起来红黑树的所有操作都比堆的更快/相等。所以我的问题是，为什么我们要在红黑树上使用堆？在我看来，红黑树可以做堆可以做的任何事情，但速度更快/相等。

谢谢。

Answer 1

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

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

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

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

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