将数组中的所有n个元素插入BST需要O(nlogn)。一个数组中的n个元素可以在O(n)时间内插入到堆中。哪一个给堆带来了明显的优势

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

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

将数组中的所有n个元素插入BST需要O(nlogn)。一个数组中的n个元素可以在O(n)时间内插入到堆中。哪一个给堆带来了明显的优势