Я очень новичок в C++, и мне было интересно, есть ли способ сделать минимальную кучу в C++ из стандартной библиотеки.
Есть ли простой способ сделать минимальную кучу в С++?
comment
Вы задаете вопросы и не принимаете ни одного. Это поведение по привычке или по выбору?
- person Siddharth   schedule 24.09.2014
Ответы (2)
Используйте 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;
}
person
wilhelmtell
schedule
07.05.2010
+1 за (тонко) указание на то, что
priority_queue
является максимальной кучей.
- person avakar; 07.05.2010
Вы можете использовать std::make_heap
, std::push_heap
и другие напрямую, или вы можете использовать std::priority_queue
, построенный на std::vector
или подобном.
Методы std::*_heap
находятся в <algorithm>
, а шаблон std::priority_queue
— в <queue>
.
person
jemfinch
schedule
07.05.2010
Чтобы уточнить:
priority_queue<X>
— это мини-куча с операциями push
и pop
для любого типа X
, который можно поместить в контейнер и который поддерживает сравнение.
- person Potatoswatter; 07.05.2010
о, так что, если бы я выскочил из priority_queue в С++, я бы получил минимальное значение?
- person Alex; 07.05.2010
Чтобы уточнить, весь шаблон
priority_queue
принимает тип контейнера, который по умолчанию равен vector<T>
. Однако подойдет любой контейнер, поддерживающий случайную итерацию и push_back
.
- person jemfinch; 07.05.2010
Если, скажем, у меня есть priority_queue‹Node›, как мне установить функцию сортировки очереди?
- person Alex; 07.05.2010
Вы бы использовали полный шаблон; перефразируя,
priority_queue<T, container, comp>
. Честно говоря, этот вопрос и ваш оригинал - это то, что вы должны сами погуглить и найти удовлетворительный ответ.
- person jemfinch; 07.05.2010
@Alex: Или просто объявите
Node::operator<
.
- person Potatoswatter; 07.05.2010
Чтобы уточнить,
priority_queue
- это max-куча, если вам нужна мини-куча, вы должны использовать std::greater
в качестве компаратора. Смотрите ответ Вильгельма.
- person avakar; 07.05.2010