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

Что такое куча?

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

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

Для чего используются двоичные кучи?

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

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

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

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

К счастью, кучи можно хранить в виде массива или списка.

  • Левый ребенок: 2n + 1
  • Правый ребенок: 2н + 2
  • n - индекс родительского узла

Например, в приведенном выше списке индекс 17 равен 3. Мы можем определить его левый дочерний элемент, выполнив вычисления: 2 (3) + 1 = 7 и его правый дочерний элемент 2 (3) +2 = 8. Его дочерние элементы расположены в массиве [7] и массиве [8], который совпадает с выше пример.

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

Реализация приоритетной очереди // Максимальная двоичная куча

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

Добавление в максимальную двоичную кучу (постановка в очередь):

  • Автоматически добавлять в конец массива, чтобы элемент «всплывал»
  • Используя отношения родитель-потомок, мы можем сравнить последнее добавление
  • Если дочерний элемент больше родительского, поменяйте местами 2 значения.

Удаление из максимальной двоичной кучи (удаление из очереди):

  • Удалите корень (это значение с наивысшим приоритетом)
  • Замените корень самым последним добавленным элементом (последним элементом)
  • Отрегулируйте кучу с помощью функции опускания
  • Подобно методу постановки в очередь, мы будем использовать отношения родитель-потомок, отмеченные выше (l: 2n + 1, r: 2n + 2), чтобы сравнивать значения корня с его дочерними элементами, пока новый корень не просочится в нужное место.

Я включил две вспомогательные функции (bubbleUp иockDown), которые изучались в курсе Colt Steele, но мы могли бы написать его прямо, без использования вспомогательных функций, это просто более читабельно, по крайней мере, для меня, чтобы сделать это таким образом.

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

BigO двоичных куч

Один из наших любимых разделов - обсуждение BigO структур данных. В чем смысл реализации двоичной кучи над массивом? Сложность времени значительно уменьшается при использовании двоичной кучи над массивом. Вставка и удаление в двоичной куче выполняются очень быстро, обе операции выполняются за O (logn) по сравнению с O (n) при использовании массивов. Очень стоит реализовать двоичную кучу, если ваша цель - постоянно добавлять и удалять узлы.

Спасибо, что не отставали от меня! На следующей неделе мы будем обсуждать хеш-таблицы.

Ресурсы: