o******0
发帖数: 105 | |
t****n
发帖数: 313 | 2 boost.heap
【在 o******0 的大作中提到】
: 自己实现？还是用priority queue?
|
l********6
发帖数: 129 | 3 pq不可以么 不行也有makeheap这些函数啊 |
w****a
发帖数: 710 | |
g*******d
发帖数: 495 | 5 之前我也是纳闷为啥没heap，最后发现如楼上说的，是 priority queue |
o******0
发帖数: 105 | 6 但如果要实现固定尺寸的min heap,比如min heap of size m.不能直接用priority_
queue吧？
【在 l********6 的大作中提到】
: pq不可以么 不行也有makeheap这些函数啊
|
l**o
发帖数: 356 | 7 Priority_queue有size（）啊，每次比较一下size，多出来的pop掉最小的不就可以了？
但如果要实现固定尺寸的min heap,比如min heap of size m.不能直接用priority_
queue吧？
【在 o******0 的大作中提到】
: 但如果要实现固定尺寸的min heap,比如min heap of size m.不能直接用priority_
: queue吧？
|
o******0
发帖数: 105 | 8 不对。应该pop掉 m 里面最大的。但没办法。
了？
【在 l**o 的大作中提到】
: Priority_queue有size（）啊，每次比较一下size，多出来的pop掉最小的不就可以了？
:
: 但如果要实现固定尺寸的min heap,比如min heap of size m.不能直接用priority_
: queue吧？
|
b**i
发帖数: 2 | 9 楼上说的对，用make_heap, pop_heap, push_heap 来做。
vector heap;
heap.push_back(1);
heap.push_back(2);
make_heap(heap.begin(), heap.end()); // 这样就把heap变成了一个max heap
auto cmp = [](int lhs, int rhs){return lhs > rhs;};
make_heap(heap.begin(), heap.end()); // 把heap变成了 min heap
下面都用minheap举例子，如果是maxheap不需要传第三个参数。
pop_heap(heap.begin(), heap.end(), cmp); // 现在 heap.back() 是heap的最上面
的那个元素，已经pop出来了
heap.push_back(998);
push_heap(heap.begin(), heap.end(), cmp); // 这样就把998正确插入到minheap了
heap的top应该可以通过front() 来访问的。 |
