How to pop min element from std::heap?

Question

I have a std::vector, that I use std::heap on it.

I want in a while loop, to pop the minimum value, every time the loop starts. In the body of the loop, another element will be inserted in the heap. The loop stops after a number of runs.

What came to my mind is to use std::sort_heap and then erase the first element. However, this doesn't seem to be a good idea. You see, speed is of real essence at this part of my code.

I don't think that this is a good idea, because I have to call std::sort_heap at every run, because an element is going to be inserting, thus making the std::vector a heap again, which means that I have to sort it again, in order the minimum element to be placed at the front.

Moreover, erasing from start, with vector.erase() is slower than erasing the last element, right? If I delete the first element, then all the others have to be moved one position to the left. If I delete the last, element, I just pay the cost of deletion.

That lead me to this idea, sort the vector my way, so that the minimum element will come to the end, thus paying the deletion of the last element only. However, this still requires sorting at every run of the loop, right?

Which is the optimal approach to tackle this problem?

Are you trying to maintain a max heap, but with the additional ability to remove the min element quickly? Or are you simply wanting a min heap? — Benjamin Lindley, Sep 17 '14 at 20:01

score 8 · Accepted Answer · edited May 23 '17 at 12:25

A std::heap sorted with std::less makes it easy to extract the largest element, not the smallest. However if you use std::greater, then you can efficiently extract the min element.

std::pop_heap, using std::greater, will put the minimum element at the back of the sequence, and reduce the size of the heap by one. You can then read the back() and write to the back() with a new element.

std::push_heap, using std::greater, will insert the element at the back of a sequence, increasing the size of the heap by one.

In code:

#include <algorithm>
#include <vector>
#include <iostream>

int
main()
{
    std::vector<int> v{5, 4, 6, 9, 0, 1, 2, 3};
    std::make_heap(v.begin(), v.end(), std::greater<int>{});
    int i;
    while (std::cin >> i)
    {
        // pop minimum, and place at back()
        std::pop_heap(v.begin(), v.end(), std::greater<int>{});
        // write min out
        std::cout << "min = " << v.back() << '\n';
        // push a new element into the heap
        v.back() = i;
        std::push_heap(v.begin(), v.end(), std::greater<int>{});
    }
}

This all quite efficient using vector because the extraction and insertion is actually at the back of the vector. And because we're using greater, we actually extract the minimum element each time (which is a little non-intuitive).

If desired, the above logic can be encapsulated in a std::priority_queue<T, std::vector<T>, std::greater<T>> which simply adapts the vector and exposes push, pop and top member functions instead of vector's push_back, pop_back and back. This adaptor will simply call make_heap, push_heap and pop_heap in the appropriate places.

Update

TemplateRex correctly points out that in C++14 greater<> can be used in place of greater<int>. For example:

std::make_heap(v.begin(), v.end(), std::greater<>{});

This creates a heterogeneous functor that can take any two arguments, not just int:

template <>
struct greater<void>
{
    template <class T1, class T2>
    auto operator()(T1&& t, T2&& u) const
        { return std::forward<T1>(t) > std::forward<T2>(u); }
    typedef void is_transparent;
};

With this new feature one only has to change the vector to change types (well, and the type of i), and the rest of the example will adapt to the change in type automatically.

or in C++14: `std::greater<>{}`, makes it easier to refactor to other types — TemplateRex, Sep 18 '14 at 13:33
@TemplateRex could you explain in a little more detail the C++14 feature you're referring to and the benefits it provides? I'm not familiar with it. — mattnewport, Sep 18 '14 at 17:00
@mattnewport [this working paper](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3421.htm) or [this Q&A](http://stackoverflow.com/questions/20317413/what-are-transparent-comparators) — TemplateRex, Sep 18 '14 at 18:11
@TemplateRex thanks, I'd heard about the heterogeneous container lookup but not the transparent comparators which actually seems more generally useful than heterogeneous lookup appeared to me initially. — mattnewport, Sep 18 '14 at 18:28

score 3 · Answer 2 · answered Sep 17 '14 at 19:54

3

I think you just want a std::priority_queue<T>. It has O(log n) complexity for push and pop.

answered Sep 17 '14 at 19:54

Bill Lynch

80,138
16
128
173

score 2 · Answer 3 · answered Sep 17 '14 at 20:02

2

Take a look at pop_heap and push_heap. As sharth suggests you can also use the priority_queue container adaptor which wraps up the heap functionality with a convenient priority queue interface.

answered Sep 17 '14 at 20:02

mattnewport

13,728
2
35
39

score 2 · Answer 4 · answered Sep 17 '14 at 20:02

std::sort_heap doesn't create a heap--rather, it takes a heap as its input, and generates fully-sorted elements as its output.

You could use a priority_queue as @Sharth has suggested. If you prefer to work directly with a heap, you can use push_heap and pop_heap to remove the smallest item and insert the new item respectively.

Note that unlike most algorithms, push_heap and pop_heap just rearrange items in a range. I.e., pop_heap moves the smallest (or largest, depending on your comparison function) item in the heap, and moves it to the end of the range, and rearranges the preceding elements into a valid heap.

Likewise, push_heap, takes a heap in one section of memory followed by one item in the next location in memory, and adds that element to the heap, so the entirety forms a valid heap again.

How to pop min element from std::heap?

4 Answers4