弱弱的问个C++用priority_queue定义min heap的问题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

弱弱的问个C++用priority_queue定义min heap的问题

弱弱的问个C++用priority_queue定义min heap的问题# JobHunting - 待字闺中

k*t2013-08-17 07:08

1 楼

知道怎么用priority_queue定义min heap, 如果heap中的元素为int, 我一般用
priority_queue, cmp> minheap, 另外再另外定义下cmp。有次面试
时，面试官问我priority_queue, cmp>中，为何需要vector，
我说是个container, 其他的我就啥也不知道啦。有人知道为何c++不把这container写
死为一个类型，比如vector? 让用户自己定义container有啥优势？除了vector, 还有
其他container可以用来定义min heap么？问的问题有点弱，请轻拍

p*n2013-08-17 07:08

2 楼

因为是int，所以直接用greater就好了，不用自己在写一个comparator
priority_queue, std::greater> minheap
另外再另外定义下cmp。有次面试
priority_queue is a container adapter in STL，vector is used to specify
the underlining container, you can also choose deque
even though priority_queue uses vector by default, here you have to
specify it because you are going to assign a comparator and hence all the
template parameters preceding comp need to be explicitly specified.
有人知道为何c++不把这container写
i think it is designed for maximum flexibility. for example, if you think
vector<> is not good enough to meet your specific needs and you have written
your own sequential container conforming to STL requirements, then you can
easily make a customized priority_queue based on it.
让用户自己定义container有啥优势？除了vector, 还有

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

: 知道怎么用priority_queue定义min heap, 如果heap中的元素为int, 我一般用
: priority_queue, cmp> minheap, 另外再另外定义下cmp。有次面试
: 时，面试官问我priority_queue, cmp>中，为何需要vector，
: 我说是个container, 其他的我就啥也不知道啦。有人知道为何c++不把这container写
: 死为一个类型，比如vector? 让用户自己定义container有啥优势？除了vector, 还有
: 其他container可以用来定义min heap么？问的问题有点弱，请轻拍

k*t2013-08-17 07:08

3 楼

学习啦，非常感谢哈

specify

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

:
: 因为是int，所以直接用greater就好了，不用自己在写一个comparator
: priority_queue, std::greater> minheap
: 另外再另外定义下cmp。有次面试
: priority_queue is a container adapter in STL，vector is used to specify
: the underlining container, you can also choose deque
: even though priority_queue uses vector by default, here you have to
: specify it because you are going to assign a comparator and hence all the
: template parameters preceding comp need to be explicitly specified.
: 有人知道为何c++不把这container写

a*m2013-08-17 07:08

4 楼

default是vector?这样的话插入和取第一个都是 O(n)了吧。

specify

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

a*m2013-08-17 07:08

5 楼

不对。用heap实现的话还是lgn，这样应该就可以了。
这样回答lz的问题就是heap需要随机访问元素。其它简单类型比如queue,stack都不符
合这个要求。

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

: default是vector?这样的话插入和取第一个都是 O(n)了吧。
:
: specify

p*n2013-08-17 07:08

6 楼

http://en.cppreference.com/w/cpp/container/priority_queue
default确实是vector
pq.push is equivalent to vec.push_back，then call ascend method to put it in
the correct position
for pq.erase, first swap vec.front() and vec.back(), then erase vec.back()
and call descend method to put vec.front() to the correct position.

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

: 不对。用heap实现的话还是lgn，这样应该就可以了。
: 这样回答lz的问题就是heap需要随机访问元素。其它简单类型比如queue,stack都不符
: 合这个要求。

a*m2013-08-17 07:08

7 楼

嗯。应该是。刚才想偏了。

in

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

: http://en.cppreference.com/w/cpp/container/priority_queue
: default确实是vector
: pq.push is equivalent to vec.push_back，then call ascend method to put it in
: the correct position
: for pq.erase, first swap vec.front() and vec.back(), then erase vec.back()
: and call descend method to put vec.front() to the correct position.