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

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

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

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