Бинарная куча и приоритетная очередь⁠⁠

Последние пару месяцев я решил попрактиковаться в решении задач на алгоритмы и структуры данных и вспомнить всё, что мы проходили в универе. Там, кстати, ни слова не было не только о сложностях алгоритмов, но и о Приоритетных очередях.

❓ Что это такое “Приоритетная очередь”

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

Приоритетная очередь поддерживает те же операции, что и обычная очередь.

❓ Что это такое “Бинарная (двоичная) куча”

Бинарная куча – структура данных, позволяющая быстро (за логарифмическое время) добавлять элементы и извлекать элемент с максимальным приоритетом.

Куча представляет собой полное бинарное дерево, в котором каждый элемент не меньше своих потомков. Таким образом, максимальный элемент всегда находится в корне, поэтому доступ к нему происходит за O(1).

Можно сказать, что приоритетная очередь — это интерфейс, а бинарная куча — одна из возможных реализаций интерфейса “приоритетной очереди”.

💡 О том, как происходит добавление и удаление элементов из бинарной кучи описано в статье на хабре Структуры данных: двоичная куча (binary heap)

🧑‍💻 Собеседования

Интересный факт, что при прохождении собеседования на вашем языке программирования такая структура данных может отсутствовать.

Например:

- В .NET 6 появилась встроенная реализация приоритетной очереди, она так и называется PriorityQueue
- А вот в JavaScript из коробки в нет подобной реализации

В таком случае можно быстро реализовать приоритетную очередь с помощью динамического массива:

- Описать класс PriorityQueue, у которого под капотом используется динамический массив
- Метод Enqueue — добавляет элемент в конец динамического массива
- Метод Dequeue — извлекает элемент с наименьшим приоритетом

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

⌨️ Пример задачи с Leetcode

Чтобы понять как и зачем использовать приоритетную очередь можно порешать следующие задачи на Leetcode

1. Top K Frequent Words
2. Top K Frequent Elements

Еще по теме:

- .NET 6: PriorityQueue
- Top K Frequent Words - Priority Queue Approach (LeetCode)

#algorithms #interview

https://t.me/cherkashindev/115