Очереди с приоритетом на основе двоичной кучи¶

В предыдущих разделах вы узнали о FIFO структуре данных - очереди. Одной из её важных вариаций является очередь с приоритетом. Она работает, как обычная очередь с удалением объекта, стоящего на первом месте, однако внутренний порядок элементов зависит от их приоритета. Те, чей приоритет выше, ставятся в начало очереди, ниже - в её конец. Таким образом, когда вы добавляете новый элемент, он может сразу же стать самым первым. Мы увидим, что очередь с приоритетом - полезная структура данных для некоторых алгоритмов на графах, которые будут изучаться в следующей главе.

Возможно, вы можете придумать несколько простых способов реализации очереди с приоритетом с использованием сортировочных функций и списков. Однако, вставка в список имеет \(O(n)\), а сортировка - \(O(n \log{n})\). Мы можем сделать лучше. Классический способ реализации очереди с приоритетом - использовать структуру данных под названием двоичная куча. Она позволит нам ставить в очередь и извлекать из неё элементы за \(O(\log{n})\).

Изучать двоичную кучу интересно потому, что если её нарисовать, то она очень похожа на дерево, но для внутреней реализации мы будем использовать обычный список. Двоичная куча имеет два различных варианта: min heap, где в начале всегда располагается наименьший ключ, и max heap, где самым первым стоит наибольший из ключей. В этом разделе мы воплотим min heap, оставив реализацию max heap в качестве упражнения.