еборе элементов кучи вы не пол

Автор admin Среда, 10 июня 2009 11:32

еборе элементов кучи вы не получите ожидаемого порядка следования элементов приоритетной очереди. Вообще говоря, нужного результата можно добиться простым вызовом функции sort_heap(), но это решение работает только один раз; после вызова куча превращается в отсортированный список. Чтобы снова использовать его как кучу, необходимо снова вызвать функцию make_heap(). Мы можем инкапсулировать этот вызов в пользовательской реализации очереди: //: С07:PriorityQueue6.срр #include #i nclude #i nclude #i nclude 386 Глава 7 • Обобщенные контейнеры linclude linclude using namespace std: tempiate class PQV : public vector { Compare comp: bool sorted: void assureHeapO { if(sorted) { // Обратное преобразование списка в кучу: make_heap(this->begin(). this->end(). comp): sorted = false: } } public: PQV (Compare cmp = CompareO) : comp(cmp) { make_heap(this->begin(). this->end(). comp): sorted – false: } const T& topO { assureHeapO; return this->front(); } void push(const T& x) { assureHeapO: this->push_back(x): // Занести элемент в