有没有一种简单的方法可以在C++中创建最小堆？

Question

我对 C++ 很陌生，我想知道是否有一种方法可以从标准库中创建 C++ 的最小堆。

Answer 1

使用

make_heap()

和朋友（在

<algorithm>

中定义），或使用

priority_queue

（在

<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;
}

Answer 2

您可以直接使用

std::make_heap

、

std::push_heap

等，也可以使用基于

std::priority_queue

或类似工具构建的

std::vector

。

std::*_heap

方法在

<algorithm>

中，

std::priority_queue

模板在

<queue>

中。

Answer 3

您可以使用 中定义的 std::priority_queue 和 . 中定义的 std::greater

例如：

#include <iostream>
#include <queue>
#include <functional>

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap();
minHeap.push(5);
minHeap.push(1);
minHeap.push(3);
minHeap.push(2);
minHeap.push(4);

while (!minHeap.empty()){
   std::cout << minHeap.top() << std::endl;
   minHeap.pop();
}

这将打印：

1
2
3
4
5