CODEWITHSUNDEEP
c++
Jishan
Jishan

Reputation: 1684

Min Heap Extract 2 Smallest Element

I have a minimum heap viz. 

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

How can I get the 2 minimum values in this heap within O(n) time, by say using just one loop?

Regards.

Upvotes: 0

Views: 916

Answers (1)

Rameshwar Bhaskaran
Rameshwar Bhaskaran

Reputation: 345

You can do it in O(logn) time once your heap is formed. You can do it with a single pop and 2 queries.

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

Looking at this will help : http://en.cppreference.com/w/cpp/container/priority_queue

Upvotes: 3

Related Questions