正如其他人所提到的，Heap可以在O(1)中执行findMin或findMax，但不能在相同的数据结构中同时执行。然而，我不同意Heap在findMin/findMax中更好。事实上，只要稍加修改，BST就可以在O(1)中同时执行findMin和findMax。

在这个修改后的BST中，每次执行可能修改数据结构的操作时，都要跟踪最小节点和最大节点。例如，在插入操作中，您可以检查最小值是否大于新插入的值，然后将最小值分配给新添加的节点。同样的技术也可以应用在最大值上。因此，这个BST包含这些信息，您可以在O(1)中检索它们。(与二进制堆相同)

在这个BST(平衡BST)中，当你弹出min或弹出max时，下一个要分配的min值是min节点的继任者，而下一个要分配的max值是max节点的前任。因此它在O(1)中执行。然而，我们需要重新平衡树，因此它仍然会运行O(log n)(与二叉堆相同)。

我很想在下面的评论中听到你的想法。谢谢:)

更新

交叉参考类似问题我们可以用二叉搜索树来模拟堆操作吗?有关使用BST模拟堆的更多讨论。

什么时候使用堆，什么时候使用BST

Heap更擅长findMin/findMax (O(1))，而BST擅长所有的查找(O(logN))。两个结构的插入值都是O(logN)。如果你只关心findMin/findMax(例如，优先级相关)，使用heap。如果你想要一切都井然有序，那就用BST吧。

这里的前几张幻灯片解释得很清楚。

堆是实现优先级队列的具体数据结构。

没有理由让分支因子固定等于2。 通常我们可以有d-ary树:

Trees that used for heap are complete trees. Heaps are created to get the highest priority element in the data. However binary search as the name says are for searching. Heaps are not good for is checking whether or not an element is stored in them. You have no other choice than going through all the elements until you find the one you are looking for, or we get to the end of the array. This means a linear time algorithm. It is O(log(n)) for binary search trees. Binary Search Tree doesn’t allow duplicates, however, the Heap does. The Binary Search Tree is ordered, but the Heap is not. Insert and remove will take O(log(n)) time in a heap. In a Binary Search Tree, this may take up to O(n) time, if the tree is completely unbalanced. In the image below you see two BSTs, right one is chained so insert and remove might take O(N) but for the left one O(Log(N))

堆可以在线性时间内构建(使用heapify)，但是，BST需要创建O(n * log(n))。 堆是完整的树。这是非常重要的事实。因为当你插入的时候你必须从最后一个插入，这样交换之后 会有完整的树形结构。类似地，当你删除时， 删除从根开始，先删除根再保留 完整的树结构中最后一个元素应该是树 插入根。

参考

二叉搜索树使用的定义是:对于每个节点，它左边的节点有一个更小的值(键)，而它右边的节点有一个更大的值(键)。

其中堆，作为二叉树的实现使用以下定义:

如果A和B是节点，其中B是A的子节点，则A的值(键)必须大于或等于B的值(键)，即: key(A)≥key(B)。

http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree

我今天考试的时候也做了这道题，我答对了。微笑……：）

BST over Heap的另一种用法;因为有一个重要的区别:

在BST中找到后继和前任将花费O(h)时间。(O(logn) in balanced BST) 而在Heap中，则需要O(n)时间才能找到某个元素的后继或前任。

在堆上使用BST:现在，假设我们使用一个数据结构来存储航班的着陆时间。如果着陆时间差值小于“d”，我们不能安排航班降落。并且假设许多航班已经安排在一个数据结构(BST或Heap)中降落。

现在，我们想安排另一个降落在t点的Flight，因此，我们需要计算t与它的继任者和前任的差值(应该是>d)。 因此，我们需要一个BST，如果平衡的话，它会很快，即在O(logn)。

编辑:

排序BST需要O(n)时间按排序顺序打印元素(内序遍历)，而Heap可以在O(n logn)时间内完成。 Heap提取最小元素并重新堆化数组，这使得它在O(n logn)时间内完成排序。

Heap只保证较高级别的元素比较低级别的元素更大(对于max-heap)或更小(对于min-heap)，而BST保证顺序(从“左”到“右”)。如果你想要排序的元素，使用BST。