弱问C++用heap的题能用multiset吗 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

弱问C++用heap的题能用multiset吗

弱问C++用heap的题能用multiset吗# JobHunting - 待字闺中

b*i2015-03-25 07:03

1 楼

问问，因为multiset实在写习惯了，新的priority_queue反而怕出bug。
请问面试的时候用multiset来代替heap可以吗（如果不要求实现heap本身的话），
multiset是基于红黑树的，复杂度应该都是log(n)的。

k*p2015-03-25 07:03

2 楼

总感觉用红黑树代替heap有点overkill。红黑树相对heap更加有序，虽然insert和
delete操作都是log(n)，但红黑树前面系数会大很多。另外heap的getmin()或getmax()
O(1), 如果这个操作比较频繁的话，最好不要用红黑树。当然你可以改进红黑树，加个
max或min变量，也能到O(1)。
priority_queue不如自己写的heap灵活，不能update节点，比如不能用来实现http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/。

b*i2015-03-25 07:03

3 楼

同意，
priority_queue不能update节点。
但我指的情况比如leetcode上面merge K sorted list那题不是要用个heap吗，这种情
况如果我就用multiset面试官会说吗？

()

【在 k****p 的大作中提到】

: 总感觉用红黑树代替heap有点overkill。红黑树相对heap更加有序，虽然insert和
: delete操作都是log(n)，但红黑树前面系数会大很多。另外heap的getmin()或getmax()
: O(1), 如果这个操作比较频繁的话，最好不要用红黑树。当然你可以改进红黑树，加个
: max或min变量，也能到O(1)。
: priority_queue不如自己写的heap灵活，不能update节点，比如不能用来实现http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/。

k*p2015-03-25 07:03

4 楼

那样可以用priority_queue。priority_queue的函数名和stack一样的,pop,push,top很
好记。
面试官怎么看，我也不清楚。面试经验不多。。。
另外那个题也可以两两merge。假设总长度N,heap复杂度O(Nlog(K))。两两merge的话
，每轮最多2N(list奇数2N,偶数N)。有log(K)轮。

【在 b******i 的大作中提到】

: 同意，
: priority_queue不能update节点。
: 但我指的情况比如leetcode上面merge K sorted list那题不是要用个heap吗，这种情
: 况如果我就用multiset面试官会说吗？
:
: ()

b*i2015-03-25 07:03

5 楼

恩，有道理，两两merge

【在 k****p 的大作中提到】

: 那样可以用priority_queue。priority_queue的函数名和stack一样的,pop,push,top很
: 好记。
: 面试官怎么看，我也不清楚。面试经验不多。。。
: 另外那个题也可以两两merge。假设总长度N,heap复杂度O(Nlog(K))。两两merge的话
: ，每轮最多2N(list奇数2N,偶数N)。有log(K)轮。