Бинарная куча и приоритетная очередь
Последние пару месяцев я решил попрактиковаться в решении задач на алгоритмы и структуры данных и вспомнить всё, что мы проходили в универе. Там, кстати, ни слова не было не только о сложностях алгоритмов, но и о Приоритетных очередях.
❓ Что это такое “Приоритетная очередь”
Приоритетная очередь — это коллекция, в которой, в отличии от обычной очереди, элементы упорядочиваются не на основе того, когда был добавлен элемент, а на основе приоритета, который этот элемент имеет. То есть, первым всегда будет извлекаться элемент с максимальным приоритетом. Также можно настроить очередь, чтобы она работала с наименьшими приоритетами.
Приоритетная очередь поддерживает те же операции, что и обычная очередь.
❓ Что это такое “Бинарная (двоичная) куча”
Бинарная куча – структура данных, позволяющая быстро (за логарифмическое время) добавлять элементы и извлекать элемент с максимальным приоритетом.
Куча представляет собой полное бинарное дерево, в котором каждый элемент не меньше своих потомков. Таким образом, максимальный элемент всегда находится в корне, поэтому доступ к нему происходит за 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
