如何从std :: heap弹出min元素？

Question

我有一个std::vector,我用std::heap它.

我希望在while循环中,每次循环开始时弹出最小值.在循环体中,另一个元素将插入堆中.循环在多次运行后停止.

我想到的是使用std::sort_heap然后擦除第一个元素.但是,这似乎不是一个好主意.你看,在我的代码的这一部分,速度是真正的本质.

我不认为这是一个好主意,因为我必须std::sort_heap在每次运行时调用,因为一个元素将要插入,从而std::vector再次成为一个堆,这意味着我必须再次对它进行排序,以便最小元素放在前面.

而且,从开始删除,vector.erase()比删除最后一个元素慢,对吗？如果我删除了第一个元素,那么所有其他元素都必须向左移动一个位置.如果我删除最后一个元素,我只需支付删除费用.

这引出了我的想法,按照我的方式对向量进行排序,以便最小元素将结束,从而仅删除最后一个元素.但是,这仍然需要在每次循环运行时进行排序,对吗？

哪种方法可以解决这个问题？

Answer 1

一个std::heap排序与std::less可以很容易地提取最大的元素,而不是最小的.但是,如果使用std::greater,则可以有效地提取min元素.

std::pop_heap,using std::greater,将最小元素放在序列的后面,并将堆的大小减小一.然后,您可以使用新元素读取back()和写入back().

std::push_heap,using std::greater,将元素插入序列的后面,将堆的大小增加一.

在代码中:

#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>{});
    }
}

这一切都非常有效,vector因为提取和插入实际上是在后面vector.因为我们正在使用greater,我们实际上每次都提取最小元素(这有点不直观).

如果需要,可以将上述逻辑封装在一个std::priority_queue<T, std::vector<T>, std::greater<T>>简单地适应vector和暴露push,pop以及top成员函数而不是vector's push_back,pop_back和back.这个适配器只需调用make_heap,push_heap并pop_heap在适当的位置.

更新

TemplateRex正确指出在C++ 14中greater<>可以代替使用greater<int>.例如:

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

这创建了一个异构的函子,可以接受任何两个参数,而不仅仅是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;
};

使用此新功能,只需更改vector更改类型(以及类型i),示例的其余部分将自动适应类型的更改.