Есть ли простой способ сделать минимальную кучу в 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>.