这是我不太明白的。当我阅读关于堆的文献时，它总是说堆的最大优点是可以立即获得最顶层(如果堆最大，则最大)元素。但是，难道不能使用BST并存储指向同一节点(最右下角)的指针，并通过插入/删除更新指针吗?
如果我没弄错的话，在我描述的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.
我在这里错过了什么?
但是您不能使用BST并存储指向同一节点的指针(最右下角)并使用插入/删除更新指针吗?
是的，你可以。
使用我所描述的BST实现，您将拥有[…]删除最大0(1)[…]让它变得更好。[…设置max的父值为null。做。
不，最大移除不会(总是)是O(1)，原因如下:
-
删除Max后，还需要更新指针以引用最右下角的节点。例如，取这个树，在移除Max之前:
8 / 5 20 <-- Max pointer / / 2 12 / 10 13 14你必须找到值为14的节点，所以要更新Max指针。
-
可以使以上操作为O(1)，通过保持树的平衡，假设根据AVL规则。在这种情况下，前一个Max节点的左子节点将没有右子节点，而新的Max节点将是它的左子节点，或者如果它没有右子节点，则是它的父节点。但是由于一些删除将使树不平衡，因此需要在它们之后进行重新平衡操作。这可能涉及到几个旋转。例如，取这个平衡的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)操作，使其与二进制堆中的相同操作具有相同的时间复杂度。
什么是二叉搜索树做不到的?
考虑到二进制堆不使用指针，因此具有更少的"管理";与自平衡BST相比，插入/删除操作的实际空间消耗和运行时间将更好，而它们的渐近复杂性是相同的。
此外，从一个非排序数组构建一个二进制堆可以在O(n)时间内完成，而构建一个BST则需要O(nlogn)时间。
然而，当你需要能够按照正确的顺序遍历值，或者找到一个值，或者找到一个值的前身/后继值时，BST是一种方法。对于此类操作，二进制堆的时间复杂度更差。
最大堆和平衡BST(例如AVL树)在O(log n)时间内执行这些操作。但是由于指针的存在，BST占用了更多的空间，而且它们的代码也更复杂。
既然你说的是BST而不是平衡BST，那么考虑一下以下倾斜BST:
1
2
3
...
n
你可以保留一个指向max (n-th)元素的指针引用，但是如果你插入一个值< n，在最坏的情况下，它将需要O(n)插入时间。此外，要查看堆中的最大值，您可以简单地执行heap[0](假设堆是使用数组实现的)来获取堆在O(1)时间内的最大元素。