二叉堆能做什么而二叉搜索树不能？

Question

这个我不太明白。当我阅读有关堆的文献时，它总是说堆的最大优势是您可以立即获得顶部（如果是最大堆则为最大）元素。但是你不能只使用 BST 并将指针存储到同一节点（最右下角）并用 insertions/deletions 更新指针吗？

如果我没记错的话，使用我描述的 BST 实现你会

================================================
                    | Insert    | Remove Max
================================================
 Special BST        | O(log(n)) |    O(1)
================================================
 Max Heap           | O(log(n)) |    O(log(n))
================================================

让它变得更好。

伪代码：

Insert:
   Same as regular BST insert, but can keep track of whether
   item inserted is max because traversal will be entirely
   in the right direction.

Delete
   Set parent of max equal to null. Done.

我在这里错过了什么？

Answer 1

最大堆和平衡 BST（例如 AVL 树）都在 O(log n) 时间内执行这些操作。但是由于指针的原因，BST 需要更多的常数因子 space 并且它们的代码更复杂。

Answer 2

由于您谈论的是 BST 而不是平衡 BST，请考虑以下倾斜的 BST：

您可以保留对最大（第 n 个）元素的指针引用，但如果您要插入值 < n，则需要 O(n) 插入时间最坏的情况。此外，要查看堆中的最大值，您可以简单地执行 heap[0]（假设堆是使用数组实现的）以在 O(1) 时间内为堆获取最大元素。

Answer 3

But couldn't you just use a BST and store a pointer to the same node (bottom-rightmost) and update the pointer with insertions/deletions?

是的，你可以。

with the BST implementation I'm describing you would have [...] Remove Max O(1) [...] making it better. [...] Set parent of max equal to null. Done.

不，最大移除量不会（总是）为 O(1)，原因如下：

移除 Max 后，还需要更新指针以引用底部 right-most 节点。例如，以这棵树为例，在删除 Max 之前：
```
        8
      /   \
     5     20   <-- Max pointer
    /     / 
   2    12
       /  \
     10    13 
             \
              14
```
您必须找到值为 14 的节点，以便更新 Max 指针。
可以使上述操作成为 O(1)，通过保持树平衡，比方说根据 AVL 规则。在那种情况下，前一个 Max 节点的左 child 将没有右 child，并且新的 Max 节点将是其左 child，或者如果它没有右 child ，其 parent。但是由于一些删除会使树不平衡，因此需要在它们之后进行重新平衡操作。这可能涉及多次轮换。例如，采用这个平衡的 BST：
```
          8
        /   \
       5     13
      / \   /  \
     2   6 9    15  <-- Max pointer
    / \   \ \
   1   4   7 10
      /
     3
```
去掉节点15后，很容易确定13是下一个Max，但是以13为根的子树会不平衡。平衡之后，整个树是不平衡的，需要再进行一次旋转。旋转次数可以是 O(logn).

结论是，您可以使用带 Max 指针的平衡 BST，但是提取 Max 节点仍然是一个 O(logn) 操作，使其时间复杂度与在二进制堆中进行相同的操作。

What can a binary heap do that a binary search tree cannot?

考虑到二叉堆不使用指针，因此“管理”开销比 self-balancing BST 少得多，insert/delete 操作的实际 space 消耗和运行时间会好一点——虽然它们的渐近复杂度是一样的。

此外，可以在 O(n) 时间内从 non-sorted 数组构建二叉堆，而构建 BST 的成本为 O(nlogn)。

但是，当您需要能够以正确的顺序遍历值、找到一个值或找到一个值的 predecessor/successor 时，BST 是必经之路。对于此类操作，二叉堆的时间复杂度更差。

二叉堆能做什么而二叉搜索树不能？

What can a binary heap do that a binary search tree cannot?

algorithm

heap

binary-tree

binary-search-tree

data-structures