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