b******i
发帖数: 914 | 1 问问，因为multiset实在写习惯了，新的priority_queue反而怕出bug。
请问面试的时候用multiset来代替heap可以吗（如果不要求实现heap本身的话），
multiset是基于红黑树的，复杂度应该都是log(n)的。 |
k****p
发帖数: 9 | 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******i
发帖数: 914 | 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****p
发帖数: 9 | 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******i
发帖数: 914 | 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)轮。
|
