h*****g
发帖数: 944 | 1 同样一组数，在做什么问题是做成heap比较好search, 做什么问题时做成BST比较好
search?
把一组数做成heap和BST,的time complexity都是O(n)吗？
能不能用o(logN)来实现一个heap或者BST?
谢了
BST = binary search tree |
l*****g
发帖数: 685 | 2 heap适用于search最大或最下k个值；BST是适用于search任意一个值
如果数组有序，构成BST的time complexity是O(n); 如果无序，是O(nlogn);
如果数组有序，那该数组本身就是个heap (ascending --> min-heap; descending -->
max-heap), 无须再改变，no time complexity; 如果数组无序，构成heap是 O(
n);
好像没有O(logn)实现heap 和 BST 的方法
【在 h*****g 的大作中提到】
: 同样一组数，在做什么问题是做成heap比较好search, 做什么问题时做成BST比较好
: search?
: 把一组数做成heap和BST,的time complexity都是O(n)吗？
: 能不能用o(logN)来实现一个heap或者BST?
: 谢了
: BST = binary search tree
|
a***9
发帖数: 364 | 3 无序数组建堆是O(n)。
->
【在 l*****g 的大作中提到】
: heap适用于search最大或最下k个值；BST是适用于search任意一个值
: 如果数组有序，构成BST的time complexity是O(n); 如果无序，是O(nlogn);
: 如果数组有序，那该数组本身就是个heap (ascending --> min-heap; descending -->
: max-heap), 无须再改变，no time complexity; 如果数组无序，构成heap是 O(
: n);
: 好像没有O(logn)实现heap 和 BST 的方法
|
l*****g
发帖数: 685 | 4 是的，谢谢指正
【在 a***9 的大作中提到】
: 无序数组建堆是O(n)。
:
: ->
|
h**********d
发帖数: 4313 | 5 需要快速access最大值和最小值的时候，用heap |
a***9
发帖数: 364 | 6 BST就是存排好序的一组数，而基于比较的排序算法没有低于O(nlogn)的。
建堆只需要O(n)，所以不能指望堆是有序的。
BST时间空间开销大，通常都是存所有的数据量，在预见需要保留所有数据
信息量的时候得用BST。堆信息量小一些，但是在处理海量数据或者流时不
好存所有数据，而且也不需要保留所有数据的信息量，只需要最大最小的k
个之类的，这时候用堆比较划算。
【在 h*****g 的大作中提到】
: 同样一组数，在做什么问题是做成heap比较好search, 做什么问题时做成BST比较好
: search?
: 把一组数做成heap和BST,的time complexity都是O(n)吗？
: 能不能用o(logN)来实现一个heap或者BST?
: 谢了
: BST = binary search tree
|
