s********u
发帖数: 1109 | 1 其实就是leetcode里的Merge k Sorted Lists
输入是一个vector lists,
但是如果用：
priority_queue, comp> heap(lists.begin(),
lists.end());
虽然编译可以过，但会runtime error。
创建一个空的heap，然后一个个push进去。这样的话理论上时间复杂度会从O(k)上升到
O(klogk)，因为直接buildheap的效率是比较高的,而每次push则需要logk。
有人用make_heap做，但直接导致整个解法繁琐不少，所以想问问可不可以用
constructor直接解决。 |
s********u
发帖数: 1109 | 2 话说需要返回头指针的题目，dummy node真是好用:) |
a******e
发帖数: 710 | 3 楼主真是精益求精~
话说merge k sorted list，瓶颈应该不在建立heap这一步吧？
假设k<
【在 s********u 的大作中提到】
: 其实就是leetcode里的Merge k Sorted Lists
: 输入是一个vector lists,
: 但是如果用：
: priority_queue, comp> heap(lists.begin(),
: lists.end());
: 虽然编译可以过，但会runtime error。
: 创建一个空的heap，然后一个个push进去。这样的话理论上时间复杂度会从O(k)上升到
: O(klogk)，因为直接buildheap的效率是比较高的,而每次push则需要logk。
: 有人用make_heap做，但直接导致整个解法繁琐不少，所以想问问可不可以用
: constructor直接解决。
|
s********u
发帖数: 1109 | 4 是的，对这道题目而言，完全没影响。
但是比如对一个数组做heapsort的时候就有影响了。。
【在 a******e 的大作中提到】
: 楼主真是精益求精~
: 话说merge k sorted list，瓶颈应该不在建立heap这一步吧？
: 假设k<
|
a******e
发帖数: 710 | 5 Heap sort 不也是nlogn么？
是的，对这道题目而言，完全没影响。但是比如对一个数组做heapsort的时候就有影响
了。。
【在 s********u 的大作中提到】
: 是的，对这道题目而言，完全没影响。
: 但是比如对一个数组做heapsort的时候就有影响了。。
|
s********u
发帖数: 1109 | 6 量级上是没有影响。
heapsort相当于是先建立一个heap,需要O(n),再removefirst n次，就是nlogn
如果第一步是通过push来操作的，那么总共就是2nlogn。
而且有的时候我看会单独问buildheap的time cost
【在 a******e 的大作中提到】
: Heap sort 不也是nlogn么？
:
: 是的，对这道题目而言，完全没影响。但是比如对一个数组做heapsort的时候就有影响
: 了。。
|
h****y
发帖数: 137 | 7 是因为vector里面可能有空指针吧
【在 s********u 的大作中提到】
: 其实就是leetcode里的Merge k Sorted Lists
: 输入是一个vector lists,
: 但是如果用：
: priority_queue, comp> heap(lists.begin(),
: lists.end());
: 虽然编译可以过，但会runtime error。
: 创建一个空的heap，然后一个个push进去。这样的话理论上时间复杂度会从O(k)上升到
: O(klogk)，因为直接buildheap的效率是比较高的,而每次push则需要logk。
: 有人用make_heap做，但直接导致整个解法繁琐不少，所以想问问可不可以用
: constructor直接解决。
|
