В качестве продолжения нашей серии по структурам данных в этой статье мы будем обсуждать двоичные кучи, и я буду включать код для реализации двоичной кучи в 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) при использовании массивов. Очень стоит реализовать двоичную кучу, если ваша цель - постоянно добавлять и удалять узлы.
Спасибо, что не отставали от меня! На следующей неделе мы будем обсуждать хеш-таблицы.
Ресурсы: