问题描述
我可以定义一个最小堆为:
I can define a min heap as:
priority_queue<int, vector<int>, greater> pq;
我有一个整数流。最小堆的大小是固定值k。看起来priority_queue不能这样做。
I have a stream of integers. The min heap's size is a fixed value k. It seems that priority_queue can not do this.
推荐答案
如果你想使用 std :: priority_queue
,将队列的大小限制为 k
元素很简单。注意,你需要使用一个最大堆,而不是一个最小堆,因为你需要知道一个新到达的值是否应该插入堆,如果它小于当前堆的最大值将发生。 / p>
If you want to use std::priority_queue
, it's trivial to limit the size of the queue to k
elements. Note however that you need to use a max heap, not a min heap, because you need to know whether a newly arrived value should be inserted into the heap, which will happen if it is smaller than the maximum value currently in the heap.
class Topk {
public:
Topk(int k) : k_(k) {}
void insert(int value) {
if (q_.size() < k_) q_.push(value);
else if (value < q_.top()) { q_.pop(); q_.push(value); }
}
std::vector<int> finalize() {
std::vector<int> result(q_.size());
while (q_.size()) {
result[q_.size() - 1] = q_.top();
q_.pop();
}
return result;
}
private:
int k_;
std::priority_queue<int> q_;
}
只是使用堆算法并不复杂:
Just using the heap algorithms is really not more complicated:
class Topk {
public:
Topk(int k) : k_(k) {}
void insert(int value) {
if (c_.size() < k_) {
c_.push_back(value);
if (c_.size() == k_) make_heap(c_.begin(), c_.end());
}
else if (value < c_[0]) {
/* See note below */
pop_heap(c_.begin(), c_.end());
c_.back() = value;
push_heap(c_.begin(), c_.end());
}
}
std::vector<int> finalize() {
if (c_.size() < k_)
std::sort(c_.begin(), c_.end());
else
sort_heap(c_.begin(), c_end());
std::vector<int> c;
std::swap(c, c_);
return std::move(c);
}
private:
/* invariant: if c_.size() == k, then c_ is a maxheap. */
int k_;
std::vector<int> c_;
}
注意:< algorithm>
不包括 heap_sift_down
操作,这对于此应用程序是不幸的;可以用swap / sift_down替换pop / swap / push操作。这仍然是O(log k),但它可能稍快一点。
Note: <algorithm>
does not include a heap_sift_down
operation, which is unfortunate for this application; the pop / swap / push operation could be replaced with swap / sift_down. That's still O(log k), but it is probably slightly faster.
这篇关于如何使用std :: priority_queue创建固定大小的最小堆?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!