为什么会选择使用堆而不是自平衡二叉搜索树？

Question

3

堆的用途是什么？堆能做的任何事情都可以由自平衡二叉搜索树（如AVL树）完成。堆最常见的用途是在O（1）时间内找到最小（或最大）元素（始终为根）。构建AVL树时也可以包括此功能，方法是保持对最小（或最大）元素的指针，并且可以在O（1）时间内回答min / max查询。

我能想到的堆比AVL树的唯一优点是，由于指针，AVL树使用更多的内存。除此之外，使用堆而不是AVL树是否有其他优点/功能？

- Siddhanjay Godre

3个回答

2

一个堆可能具有更好的插入和合并时间。这实际上取决于堆的类型，但通常它们比AVL更灵活，因为它们不必担心每个操作后的自动平衡。

堆仅保证所有节点在堆中遵循相同的排序样式。当然还有更严格的堆，如二叉堆，由于排序更重要，因此使插入和合并更加困难，但并非总是如此。

例如，Fibonacci堆的插入和合并时间为O(1)，而AVL为O(log n)。

与堆相比，构建完整的AVL也更加困难。

我们通常在只想快速访问最小值和最大值项并且不关心其他元素的完美排序时使用堆。通过快速插入，我们可以快速处理许多元素，并始终将注意力集中在最重要（或最不重要）的元素上。

- Eric Hotinger

1

当您说自平衡二叉树比堆做更多的事情且堆使用更少的指针时，您是正确的。以下是一些额外的考虑：

- Nayuki

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

主要原因是二叉堆实际上是用数组而不是树来实现的（树只是一种比喻，实际实现是一个数组，其中元素下标为i的子节点是下标为2i+1和2i+2的元素）。数组比树在空间和时间上都更加高效（常数方面），这是由于引用局部性，使得数据结构更加缓存高效，通常会产生更好的常数。

此外，使用n个元素初始化二叉堆需要O(n)的时间，而对于BST则需要O(nlogn)的时间。