为什么要在自平衡二叉搜索树上使用堆？
Why would one use a heap over a self balancing binary search tree?
堆有什么用？堆可以做的事情也可以通过像 AVL 树这样的自平衡二叉搜索树来完成。堆最常见的用途是在 O(1) 时间内找到最小（或最大）元素（它总是根）。通过维护指向最小（或最大）元素的指针构造 AVL 树时也可以包含此功能，并且可以在 O(1) 时间内回答 min/max 查询.
我能想到的堆相对于 AVL 树的唯一好处是 AVL 树因为指针使用了更多的内存。是否还有其他 advantage/functionality 在 AVL 树上使用堆？
当您说自平衡二叉树可以比堆做更多的事情并且堆使用较少 space 的指针时，您是正确的。以下是一些额外的注意事项：
二叉堆比 AVL 树需要更少的代码来实现。这使得编码、调试和修改变得更加容易。
一棵 AVL 树使用一个对象容器和两个指针来存储每个数据项。二进制堆对每个存储的数据项使用零开销 - 它全部打包到一个数组中。
主要原因是二叉堆实际上是作为一个数组实现的，而不是一棵树（树是一个比喻，实际实现是一个数组，其中索引为i的元素的子元素是元素索引 2i+1 和 2i+2）。数组在 space 和时间上都比树更有效（在常量方面）——由于 locality of reference，使数据结构的缓存效率更高，这通常会产生更好的常量。
此外，initializing a binary heap 和 n 元素需要 O(n) 时间，而对 BST 做同样的事情需要 O(nlogn) 时间。
堆可能有更好的插入和合并时间。它实际上取决于堆的类型，但通常它们远没有 AVL 严格，因为它们不必担心每次操作后的自动平衡。
堆仅保证所有节点在整个堆中都遵循相同的排序方式。当然还有更严格的堆，比如二叉堆，因为顺序更重要，所以插入和合并更加困难，但情况并非总是如此。
例如，Fibonacci 堆的插入和合并时间为 O(1) 与 AVL 的 O(log n)。
与堆相比，构建完整的 AVL 也更加困难。
当我们只想快速访问最小和最大项目而不关心其他元素的完美排序时，我们通常会使用堆。通过快速插入，我们可以快速处理许多元素，并始终将注意力集中在最重要（或最不重要）的元素上。
堆有什么用？堆可以做的事情也可以通过像 AVL 树这样的自平衡二叉搜索树来完成。堆最常见的用途是在 O(1) 时间内找到最小（或最大）元素（它总是根）。通过维护指向最小（或最大）元素的指针构造 AVL 树时也可以包含此功能，并且可以在 O(1) 时间内回答 min/max 查询.
我能想到的堆相对于 AVL 树的唯一好处是 AVL 树因为指针使用了更多的内存。是否还有其他 advantage/functionality 在 AVL 树上使用堆？
当您说自平衡二叉树可以比堆做更多的事情并且堆使用较少 space 的指针时，您是正确的。以下是一些额外的注意事项：
二叉堆比 AVL 树需要更少的代码来实现。这使得编码、调试和修改变得更加容易。
一棵 AVL 树使用一个对象容器和两个指针来存储每个数据项。二进制堆对每个存储的数据项使用零开销 - 它全部打包到一个数组中。
主要原因是二叉堆实际上是作为一个数组实现的，而不是一棵树（树是一个比喻，实际实现是一个数组，其中索引为i的元素的子元素是元素索引 2i+1 和 2i+2）。数组在 space 和时间上都比树更有效（在常量方面）——由于 locality of reference，使数据结构的缓存效率更高，这通常会产生更好的常量。
此外，initializing a binary heap 和 n 元素需要 O(n) 时间，而对 BST 做同样的事情需要 O(nlogn) 时间。
堆可能有更好的插入和合并时间。它实际上取决于堆的类型，但通常它们远没有 AVL 严格，因为它们不必担心每次操作后的自动平衡。
堆仅保证所有节点在整个堆中都遵循相同的排序方式。当然还有更严格的堆，比如二叉堆，因为顺序更重要，所以插入和合并更加困难，但情况并非总是如此。
例如，Fibonacci 堆的插入和合并时间为 O(1) 与 AVL 的 O(log n)。
与堆相比，构建完整的 AVL 也更加困难。
当我们只想快速访问最小和最大项目而不关心其他元素的完美排序时，我们通常会使用堆。通过快速插入，我们可以快速处理许多元素，并始终将注意力集中在最重要（或最不重要）的元素上。