Список в очередь приоритетов

Question

У меня есть проект по программированию для колледжа на C ++, разделенный на две части. Я начинаю вторую часть, где предполагается использовать priority_queues, hash tables и BST.

У меня проблемы (по крайней мере) с приоритетными очередями, так как я вынужден переделать много кода, уже реализованного в первой части.

Проект о внедрении простой системы управления аэропортом , и поэтому у меня есть классы, такие как Аэропорт (основной класс), Самолет, Терминал и Полет. В моем аэропорту было list терминалов, но теперь в спецификации проекта указано, что я должен держать терминалы в priority_queue, где на вершине находится терминал менее занятый, т.е.

Для каждого класса у меня есть функции CRUD, но как мне теперь, например, отредактировать терминал и добавить в него полет? Со списком мне просто нужно было перейти к определенной позиции, но теперь у меня есть доступ только к объекту в верхней части очереди. Решение, о котором я думал, состояло в том, чтобы скопировать терминалы очереди с приоритетами во временный список, но, честно говоря, мне не нравится этот подход.

Что мне делать?

Заранее спасибо.

Answer 1

Похоже, вам нужна приоритетная очередь с эффективным увеличением и уменьшением ключевых операций. Возможно, вам лучше создать собственную реализацию очереди приоритетов.

Контейнер priority_queue отлично подходит для динамических наборов. Но так как количество терминалов в аэропорту в значительной степени фиксировано, вы можете использовать контейнер фиксированного размера с семейством алгоритмов кучи.

В качестве внутреннего хранилища вы можете использовать любой контейнер, который предоставляет итераторы с произвольным доступом (vector, array, deque). Затем используйте семейство функций make_heap (), sort_heap () для хипификации массива. Теперь вы можете дешево получить доступ к top (), изменить приоритет случайного члена в куче и легко перебрать все элементы.

Для примера см .: http://www.cplusplus.com/reference/algorithm/make_heap/