1. Я должен поговорить о бинарных деревьях
Чтобы понять кучу, вы должны сначала понять бинарное дерево. В информатике бинарное дерево представляет собой структуру дерева с максимум двух подтереев на узел. Обычно подтерей называется «левой поддерево» и «правой поддерево». Бинарные деревья часто используются для реализации бинарных поисковых деревьев и бинарных кучей.
Каждый узел бинарного дерева имеет не более двух подделев (узлы с градусами, превышающими 2). Подделы двоичного дерева можно разделить на левое и справа, а порядок не может быть обращен. I -Th -слой бинарного дерева имеет не более 2i - 1 узлом; Бинарное дерево с глубиной k имеет не более 2k - 1 узел; Для любого двоичного дерева T, если количество терминальных узлов составляет N0, а количество узлов со степенью 2 составляет n2, n0 = n2 + 1.
Есть три основных различия между деревом и бинарным деревом:
Количество узлов в дереве составляет не менее 1, в то время как количество узлов в двоичном дереве может быть 0.
В дереве нет ограничения на максимальную степень узлов, в то время как максимальная степень узлов в бинарном дереве составляет 2
Нет разницы между левым и правым в узлах дерева, в то время как нет разницы между левым и правым в узлах двоичного дерева.
Бинарные деревья разделены на полные бинарные деревья и полные бинарные деревья.
Полное двоичное дерево: дерево с глубиной k и имеет узел 2K - 1, называется полным двоичным деревом
(Полное двоичное дерево с глубиной 3)
Полное двоичное дерево: двоичное дерево с N -узлами с глубиной k. Он называется полным двоичным деревом, когда и только тогда, когда каждый из его узлов соответствует узлу с номерами последовательностей от 1 до N в полном двоичном дереве с глубиной k.
(Полное двоичное дерево с глубиной 3)
2. Что такое куча?
Куча (двоичная куча) может рассматриваться как полное двоичное дерево. «Превосходное» свойство полного двоичного дерева состоит в том, что, за исключением нижнего слоя, каждый слой заполнен, что позволяет представленной куче массива (обычные общие двоичные деревья обычно представлены связанными списками в качестве основных контейнеров), и каждый узел соответствует элементу в массиве.
На следующем рисунке показана взаимосвязь между кучей и массивом
(Отношения между кучей и массивом)
Для заданного подписания I узла его можно легко рассчитать для подсказки родительского узла и узела ребенка этого узла:
Родитель (i) = пол (i/2), подписка родительского узла I
Слева (i) = 2i, подписание левого дочернего узла I
Справа (i) = 2i + 1, подписка на правильный детский узлы I
Как правило, существует два типа двоичных кучей: самая большая куча и самая маленькая куча.
Максимальная куча:
Максимальное значение элемента в максимальной куче отображается в корневом узле (верхняя часть кучи)
Значение элемента каждого родительского узла в куче больше или равно его дочернему узлу (если он существует)
(Максимальная куча)
Минимальная куча:
Минимальное значение элемента в минимальной кучи появляется в корневом узле (верхняя часть кучи)
Значение элемента каждого родительского узла в куче меньше или равно его дочернему узлу (если он существует)
(Минимальный стек)
3. Принцип сортировки кучи
Сортировка кучи состоит в том, чтобы снять максимальное количество в верхней части максимальной кучи, продолжить регулировать оставшуюся кучу до максимальной кучи и снова вывести максимальное число в верхней части кучи. Этот процесс продолжается до тех пор, пока не будет только оставшееся число. Определите следующие операции в куче:
Max-Heapify: отрегулируйте конечный узел кучи, чтобы узел дочернего узела всегда меньше родительского узла
Создайте максимальную кучу (Build-Max-HEAP): Перезаряйте все данные кучи, чтобы сделать ее максимальной кучей
Хип-сорта: удалите корневой узел первых данных и выполните рекурсивную работу максимальной регулировки кучи
Прежде чем продолжить следующее обсуждение, одна из проблем, которую необходимо отметить: все массивы основаны на нулевом уровне, что означает, что наша модель структуры данных кучи изменится.
(На основе нуля)
Соответственно, несколько формул расчета также должны быть скорректированы соответственно:
Родитель (i) = floor ((i-1)/2), подписка родительского узла I
Слева (i) = 2i + 1, подписание левого ребенка I.
Справа (i) = 2 (i + 1), подписание подписанного узла дочернего узла I
Функция регулировки максимальной кучи (MaxHeapify) состоит в том, чтобы поддерживать свойства самой большой кучи и является основной подпрограммой для создания самой большой кучи. Процесс работы показан на рисунке:
(Max-Heapify)
Поскольку куча все еще нарушает природу кучи после одной регулировки, требуется рекурсивное тестирование, чтобы вся куча удовлетворила природу кучи. Это может быть выражен в JavaScript следующим образом:
/** * Проверьте из индекса и поддерживайте максимальные свойства кучи * * @Array * * Запуск индекса @Index проверяет * * @Heapsize размер кучи * **/Функция maxHeApify (массив, индекс, Heapize) {var iMax = index, ilft = 2 * index + 1, iright = 2 * (index + 1); if (ilft <heApsize && array [index] <array [ilft]) {imax = ilft; } if (iright <heApsize && array [imax] <array [iright]) {imax = iright; } if (imax! = index) {swap (массив, imax, index); maxHeapify (массив, iMax, HeapiSize); // Рекурсивная регулировка}} Функциональный подмен (массив, i, j) {var temp = array [i]; Array [i] = Array [j]; Array [j] = temp;}Вообще говоря, рекурсия в основном используется в методе деления и лечения, и здесь нет необходимости в разделении и лечении. Кроме того, рекурсивные вызовы требуют нажатия/очистки стека, что имеет небольшой недостаток в производительности по сравнению с итерацией. Конечно, это можно игнорировать в соответствии с правилом 20/80. Но если вы думаете, что использование рекурсии заставит вас чувствовать себя некомфортно, вы также можете использовать итерацию, например, следующее:
/** * Проверьте из индекса и поддерживайте максимальные свойства кучи * * @Array * * Запуск индекса @Index проверяет * * @Heapsize размер кучи * **/Функция maxHeapify (массив, индекс, Heapize) {var iMax, ileft, iright; while (true) {imax = index; ilft = 2 * index + 1; iright = 2 * (index + 1); if (ilft <heApsize && array [index] <array [ilft]) {imax = ilft; } if (iright <heApsize && array [imax] <array [iright]) {imax = iright; } if (imax! = index) {swap (массив, imax, index); index = iMax; } else {break; }}} function swap (массив, i, j) {var temp = array [i]; Array [i] = Array [j]; Array [j] = temp;}Целью создания максимальной кучи (сборка Max-HEAP) является преобразование массива в максимальную кучу, принимая два параметра массива и размер кучи. Build-Max-Heap позвонит Max-Heapify снизу вверх, чтобы преобразовать массив и построить максимальную кучу. Поскольку Max-Heapify может гарантировать, что узлы после подписки я соответствует свойствам самой большой кучи, снизу вверх вызов Max-Heapify может сохранить это свойство во время процесса преобразования. Если максимальный элемент номера кучи равен N, то Build-Max-HEAP вызывает максимум Heapify в последовательности от Parent (n). Процесс заключается в следующем:
Описание следующим образом в JavaScript:
функция BuildMaxHeap (Array, Heapize) {var i, iparent = math.floor ((Heapize - 1) / 2); for (i = iparent; i> = 0; i--) {maxHeapify (массив, i, Heapsize); }}Heap-Sort-это алгоритм интерфейса для сортировки кучи. Heap-Sort сначала вызывает Build-Max-HEAP, чтобы преобразовать массив в максимальную кучу, затем обменивается верхним и нижним элементами кучи, затем поднимается внизу и, наконец, вызывает максимальную экспертиза, чтобы поддерживать максимальные свойства кучи. Поскольку верхний элемент кучи должен быть самым большим элементом в куче, после одной операции, самый большой элемент, присутствующий в куче, отделен от кучи от кучи, и после повторного n-1 массив расположен. Весь процесс заключается в следующем:
Описание следующим образом в JavaScript:
функция Heapsort (Array, Heapize) {buildMaxHeap (массив, Heapsize); for (int i = Heapize-1; i> 0; i--) {swap (массив, 0, i); maxheapify (массив, 0, i); }}4. Реализация языка JavaScript
Наконец, организуйте вышеуказанный в полный код JavaScript следующим образом:
Функция Heapsort (Array) {Function Swap (Array, i, J) {var temp = array [i]; Array [i] = Array [j]; Array [j] = temp; } function maxHeapify (массив, индекс, Heapize) {var iMax, ileft, iright; while (true) {imax = index; ilft = 2 * index + 1; iright = 2 * (index + 1); if (ilft <heApsize && array [index] <array [ilft]) {imax = ilft; } if (iright <heApsize && array [imax] <array [iright]) {imax = iright; } if (imax! = index) {swap (массив, imax, index); index = iMax; } else {break; }}} функция buildmaxHeap (array) {var i, iparent = math.floor (array.length / 2) - 1; for (i = iparent; i> = 0; i--) {maxHeapify (массив, i, array.length); }} sort sort (array) {buildmaxHeap (массив); for (var i = array.length-1; i> 0; i--) {swap (массив, 0, i); maxheapify (массив, 0, i); } return Array; } return sort (массив);}5. Применение алгоритма сортировки кучи
(1) Алгоритм производительность/сложность
Сложность времени сортировки кучи очень стабильна (мы видим, что она не чувствительна к входным данным), и является сложностью O (nn), лучший случай такой же, как и худший случай.
Однако его пространственная сложность варьируется в зависимости от реализации. Приведенные выше обсуждаются две общие сложности: O (n) и O (1). Основываясь на принципе сохранения пространства, я рекомендую метод сложности O (1).
(2) Стабильность алгоритма
Существует большое количество процессов фильтрации и перемещения в сортировке кучи, которые принадлежат нестабильному алгоритму сортировки.
(3) Алгоритм применимый сценарий
Сортировка кучи будет нести относительно большие накладные расходы в процессе построения кучи и регулировки кучи, и это не применимо, когда есть несколько элементов. Однако, когда есть много элементов, это все еще хороший выбор. Особенно при решении таких задач, как «количество лучших в больших», это почти предпочтительный алгоритм.