在C++中有简单的方法制作小根堆吗？

Question

我对C++很陌生，不知道是否有一种方式可以使用标准库在C++中创建一个小根堆。

- Alex

---

你提出问题却不接受答案，这种行为是习惯还是选择？ - Siddharth

Answer 1

使用定义在<algorithm>中的make_heap()和相关函数，或者使用定义在<queue>中的priority_queue。 priority_queue 在底层使用了make_heap和相关函数。

#include <queue> // functional,iostream,ctime,cstdlib
using namespace std;

int main(int argc, char* argv[])
{
    srand(time(0));
    priority_queue<int,vector<int>,greater<int> > q;
    for( int i = 0; i != 10; ++i ) q.push(rand()%10);
    cout << "Min-heap, popped one by one: ";
    while( ! q.empty() ) {
        cout << q.top() << ' ';  // 0 3 3 3 4 5 5 6 8 9
        q.pop();
    }
    cout << endl;
    return 0;
}

- wilhelmtell

---

+1 是在（微妙地）指出priority_queue是一个最大堆。 - avakar

Answer 2

你可以直接使用std::make_heap、std::push_heap等函数，或者使用基于std::vector的std::priority_queue容器。 std::*_heap方法在<algorithm>头文件中，而std::priority_queue模板在<queue>头文件中。

- jemfinch

---

哦，如果我从C++的priority_queue中弹出元素，那么我会得到最小值？ - Alex

进一步澄清，priority_queue的整个模板接受一个容器类型，默认为vector<T>。然而，任何支持随机迭代和push_back的容器都可以。 - jemfinch

如果我有一个priority_queue<Node>，我该如何设置队列的排序函数？ - Alex

你可以使用完整的模板；换句话说， priority_queue<T, container, comp>。这个问题和你原来的问题，老实说，都应该可以自己通过谷歌搜索找到令人满意的答案。 - jemfinch

@Alex：或者简单地声明Node::operator<。 - Potatoswatter

为了更加明确，priority_queue是一个大根堆，如果你想要一个小根堆，你需要使用std::greater作为比较器。请参考Wilhelm的回答。 - avakar