public: - public:
- priority_queue(const Compare& х = Compare()): c(), comp(х) { }
- template
- priority_queue(InputIterator first, InputIterator last,
- const Compare& х = Compare()): c(first, last), comp(x)
- { make_heap( c.begin(), с.end(), comp); }
- bool empty() const { return c.empty();}
- size_type size() const { return c.size(); }
- const value_type& top() const { return c.front();}
- void push(const value_type& х) {
- c.push_back(х);
- push_heap(c.begin(), c.end(), comp);
- }
- void pop() {
- pop_heap(c.begin(), c.end(), comp);
- с.рор_bасk();
- }
- }; // Никакое равенство не полагается
- Очереди с приоритетом - это тип контейнерных адаптеров, специально разработанных таким образом, чтобы его первый элемент всегда был самым большим из содержащихся в нем элементов, в соответствии с каким-то критерием упорядочивания.
- Контекст использования этого адаптера похож на кучу, где элементы могут быть вставлены в любой момент, и только максимальный элемент кучи может быть извлечен (тот, который находится сверху в очереди приоритетов).
- Очереди с приоритетом реализуются в виде контейнерных адаптеров, которые представляют собой классы, использующие инкапсулированный объект конкретного контейнерного класса в качестве своего базового контейнера, предоставляющего определенный набор функций-членов для доступа к своим элементам.
Способы реализации очереди с приоритетами - В очереди с приоритетами каждому элементу ставится в соответствие приоритет (весовой коэффициент).
- Очередь с приоритетами может быть реализована одним из двух способов:
- - очередь с приоритетным включением. В этом случае элемент, который добавляется в очередь, сразу размещается в ней в соответствии с его приоритетом. При удалении, этот элемент просто отсекается с конца очереди;
- - очередь с приоритетным исключением. В этом случае новый элемент просто добавляется в конец очереди. А вытягивание элемента из очереди осуществляется по его приоритету, то есть вытягивается элемент с наивысшим приоритетом.
Do'stlaringiz bilan baham: |
