C++里如何将一个vector转换成priority_queue - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

C++里如何将一个vector转换成priority_queue

C++里如何将一个vector转换成priority_queue# JobHunting - 待字闺中

s*u2013-10-01 07:10

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*u2013-10-01 07:10

2 楼

话说需要返回头指针的题目，dummy node真是好用:)

a*e2013-10-01 07:10

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*u2013-10-01 07:10

4 楼

是的，对这道题目而言，完全没影响。
但是比如对一个数组做heapsort的时候就有影响了。。

【在 a******e 的大作中提到】

: 楼主真是精益求精~
: 话说merge k sorted list，瓶颈应该不在建立heap这一步吧？
: 假设k<

a*e2013-10-01 07:10

5 楼

Heap sort 不也是nlogn么？

是的，对这道题目而言，完全没影响。但是比如对一个数组做heapsort的时候就有影响
了。。

【在 s********u 的大作中提到】

: 是的，对这道题目而言，完全没影响。
: 但是比如对一个数组做heapsort的时候就有影响了。。

s*u2013-10-01 07:10

6 楼

量级上是没有影响。
heapsort相当于是先建立一个heap,需要O(n),再removefirst n次，就是nlogn
如果第一步是通过push来操作的，那么总共就是2nlogn。
而且有的时候我看会单独问buildheap的time cost

【在 a******e 的大作中提到】

: Heap sort 不也是nlogn么？
:
: 是的，对这道题目而言，完全没影响。但是比如对一个数组做heapsort的时候就有影响
: 了。。