正如其他人所提到的，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模拟堆的更多讨论。

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

没有理由让分支因子固定等于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

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

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

正如其他人所提到的，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模拟堆的更多讨论。

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