Min堆提取2个最小元素

Question

我有一个最低限度的堆。

priority_queue<double, vector<double>, greater<double>> min_heap;
// push vector values to heap
for (const auto& e : rand)
    min_heap.push(e);

如何在O(n)时间内获得堆中的两个最小值，例如只使用一个循环？

致以问候。

Answer 1

一旦堆形成，您就可以在O(logn)时间完成它。您可以通过一个pop和两个查询来完成它。

int min1 = min_heap.top(); //get the minimum element
min_heap.pop(); //pop the minimum element from the heap
int min2 = min_heap.top(); //get the second minimum element(the new top)
min_heap.push(min1); //push the old 'top' to restore the heap to its old state

看看这个会有帮助的：queue