堆和BST的区别是什么?
什么时候使用堆，什么时候使用BST?
如果你想以排序的方式获取元素，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))。 堆是完整的树。这是非常重要的事实。因为当你插入的时候你必须从最后一个插入，这样交换之后 会有完整的树形结构。类似地，当你删除时， 删除从根开始，先删除根再保留 完整的树结构中最后一个元素应该是树 插入根。
参考
其他回答
什么时候使用堆，什么时候使用BST
Heap更擅长findMin/findMax (O(1))，而BST擅长所有的查找(O(logN))。两个结构的插入值都是O(logN)。如果你只关心findMin/findMax(例如，优先级相关)，使用heap。如果你想要一切都井然有序，那就用BST吧。
这里的前几张幻灯片解释得很清楚。
二叉搜索树使用的定义是:对于每个节点，它左边的节点有一个更小的值(键)，而它右边的节点有一个更大的值(键)。
其中堆，作为二叉树的实现使用以下定义:
如果A和B是节点，其中B是A的子节点，则A的值(键)必须大于或等于B的值(键)，即: key(A)≥key(B)。
http://wiki.answers.com/Q/Difference_between_binary_search_tree_and_heap_tree
我今天考试的时候也做了这道题，我答对了。微笑……：）
Heap只保证较高级别的元素比较低级别的元素更大(对于max-heap)或更小(对于min-heap)，而BST保证顺序(从“左”到“右”)。如果你想要排序的元素，使用BST。
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)时间内完成排序。
堆是实现优先级队列的具体数据结构。
没有理由让分支因子固定等于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))。 堆是完整的树。这是非常重要的事实。因为当你插入的时候你必须从最后一个插入，这样交换之后 会有完整的树形结构。类似地，当你删除时， 删除从根开始，先删除根再保留 完整的树结构中最后一个元素应该是树 插入根。
参考
