最小ヒープ抽出2最小要素

Question

私は最小ヒープを持っています。私はO(n)時間内に、ただ一つのループを使用して言うことで、このヒープ内の2つの最小値を取得できますか

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

？

よろしくお願いいたします。

Answer 1

ヒープが形成されたら、O(logn)時間に実行できます。あなたは1つのポップと2つのクエリでそれを行うことができます。

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 

するのに役立ちます。この見れ：http://en.cppreference.com/w/cpp/container/priority_queue