堆和BST的区别是什么?
什么时候使用堆,什么时候使用BST?
如果你想以排序的方式获取元素,BST比堆更好吗?
堆和BST的区别是什么?
什么时候使用堆,什么时候使用BST?
如果你想以排序的方式获取元素,BST比堆更好吗?
当前回答
二叉搜索树使用的定义是:对于每个节点,它左边的节点有一个更小的值(键),而它右边的节点有一个更大的值(键)。
其中堆,作为二叉树的实现使用以下定义:
如果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。
将数组中的所有n个元素插入BST需要O(nlogn)。一个数组中的n个元素可以在O(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吧。
这里的前几张幻灯片解释得很清楚。