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

В компьютерных науках приоритетная очередь — это абстрактный тип данных, поддерживающий несколько полезных операций:

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

Это определение определяет не то, как реализована приоритетная очередь, а то, что она должна делать. Теперь давайте посмотрим, как это можно было бы сделать на самом деле.

Базовая структура данных

Очередь с приоритетом может быть реализована с использованием различных структур данных, и временные сложности операций, которые мы с ней выполняем, будут зависеть от базовой реализации. В очень популярной и простой реализации используется бинарная куча. По сути, это бинарное дерево с парой специальных свойств.

Свойство 1

Все уровни дерева заполнены узлами, кроме нижнего, который может быть неполным, но все узлы в нем должны располагаться строго слева.

Свойство 2

Если мы назначим приоритеты узлам в бинарном дереве, каждый элемент будет иметь более высокий или равный приоритет, чем его дочерние узлы.

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

  • Вставьте элемент: O(log n)
  • Получить элемент с наивысшим приоритетом: O(1)
  • Удалить элемент с наивысшим приоритетом: O(log n)

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

Операции в куче

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

Вставка нового элемента

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

Затем нам нужно поместить этот новый узел P в место, где он не нарушает свойство номер 2: каждый узел имеет более высокий или равный приоритет, чем его дочерние элементы. Возможно, новый узел P имеет более высокий приоритет, чем его текущий родитель. Если это так, мы должны поменять местами узел P с его текущим родителем. В своем новом положении узел P может по-прежнему нарушать свойство номер 2, поэтому нам, возможно, придется повторить операцию обмена с его новым родителем. Мы останавливаемся, когда свойство 2 больше не нарушается, что может означать, что узел P стал корнем дерева.

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

Получение элемента с наивысшим приоритетом

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

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

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

Удаление элемента с наивысшим приоритетом

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

Чтобы исправить это, мы будем всплывать узел R в корне до тех пор, пока он не окажется в хорошем положении — таком, который не нарушает свойство 2. Для этого нам нужно посмотреть на дочерние элементы R и получить тот, у которого более высокий приоритет — S , Если есть только один дочерний узел, то это будет узел S для нас. Затем мы проверяем, выше ли приоритет S приоритета R. Если это так, мы меняем местами R и S, в противном случае мы останавливаемся. Если узел R только что поменялся местами со своим дочерним элементом S, мы повторим описанную выше операцию. Мы продолжаем повторять это и спускаться вниз по узлу R до тех пор, пока он либо не перестанет нарушать свойство 2 кучи, либо вообще не будет иметь потомков.

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

В худшем случае потребуется, чтобы узел R достиг нижнего уровня двоичной кучи. Это означает, что он будет проходить все уровни дерева, начиная с корня. Поскольку двоичная куча имеет log(n) уровней, это означает, что вся операция имеет временную сложность O(log n).

Реализация кода

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

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

Чтобы реализовать приоритетную очередь с двоичной кучей, мы можем использовать простой массив для представления двоичного дерева. Если индексы массива начинаются с 0, то корневой узел будет сохранен в этой позиции 0 массива. Его дочерние элементы будут следовать за ним, и они будут в позициях 1 и 2. Потомки узла в позиции 1 будут в позициях 3 и 4 и так далее. Идея состоит в том, чтобы последовательно хранить узлы в массиве, как если бы мы просматривали дерево сверху вниз и каждый уровень слева направо.

При таком представлении легко вычислить индексы дочерних узлов данного узла. Если узел имеет индекс X, то его дочерние индексы в массиве будут 2*X+1 и 2*X+2. Чтобы получить индекс родителя узла с индексом X, нам нужно будет вычислить (X-1)/2, где это целочисленное деление. Если бы индексы массива были основаны на 1, приведенные выше вычисления выглядели бы немного иначе, но все равно работали бы хорошо. Хорошо то, что мы можем получить целочисленное деление на два и умножение на два, если просто сдвинем номер индекса на 1 бит вправо или влево соответственно.

Имея в виду это представление, давайте сначала посмотрим на код C++. Мы будем использовать вектор для хранения значений узлов кучи. Вы можете использовать простой массив, но вам нужно знать его максимально ожидаемый размер, чтобы заранее выделить достаточно памяти.

Реализация C++ немного длинновата со всеми комментариями и шаблонами, поэтому вот ссылка на суть Github. Это должно быть понятно, учитывая приведенное выше описание и комментарии в коде.

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

При использовании Python мы можем использовать список для хранения кучи и применить те же идеи, что и в реализации C++. Вот ссылка на суть, реализующую то же самое на Python.

Примеры проблем

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

Еще одно интересное использование очереди с приоритетом — эта задача в Leetcode. Использование структуры данных позволяет добиться достаточно быстрого алгоритма, укладывающегося во временные ограничения.

Еще одним примером является задача хранения информации о медиане потока чисел, где в произвольном порядке повторяются две возможные операции: 1) добавить новый элемент и 2) получить медиану добавленных к настоящему времени чисел. Использование двух очередей с приоритетом, одна из которых содержит меньшую половину чисел, а другая — большую половину, может помочь нам вставить новые числа и иметь возможность возвращать медиану за постоянное время. Попробуйте решить это здесь или посмотрите решение, если застряли.

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

Последние мысли

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

Мы должны упомянуть здесь, что есть другие реализации, которые обеспечивают лучшую теоретическую временную сложность, чем те, которые мы достигли выше. Одним из таких примеров является использование кучи Фибоначчи, которая обеспечивает постоянное амортизированное время операций вставки. Это определенно стоит проверить, но мы решили сосредоточиться на реализации бинарной кучи выше, потому что ее действительно легко реализовать и на практике может быть быстрее из-за гораздо меньшего постоянного коэффициента. Стандартная библиотека C++, например, имеет класс priority_queue, который реализован с использованием бинарной кучи внизу.

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

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