C++里如何将一个vector转换成priority_queue# JobHunting - 待字闺中
s*u
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直接解决。
输入是一个vector
但是如果用:
priority_queue
lists.end());
虽然编译可以过,但会runtime error。
创建一个空的heap,然后一个个push进去。这样的话理论上时间复杂度会从O(k)上升到
O(klogk),因为直接buildheap的效率是比较高的,而每次push则需要logk。
有人用make_heap做,但直接导致整个解法繁琐不少,所以想问问可不可以用
constructor直接解决。