Добро пожаловать в мой учебник по чудесному, загадочному и волшебному алгоритму сортировки кучи (HSA), который мы создадим с помощью JavaScript.
Вступление
Я буду честен, для любых младших разработчиков, которые не знакомы с деревьями двоичного поиска, макс / мин кучей и другими связанными понятиями, это будет довольно сложное пошаговое руководство. Мое предложение: не торопитесь с каждым шагом и убедитесь, что вы твердо усвоили основы по мере продвижения по материалу. И как красноречиво выразился Сэмюэл Л. Джексон ...
«Держись за свои задницы» (Парк Юрского периода, 1993)
Рассмотрение
Хорошо, обо всем по порядку, прежде чем мы сможем правильно определить, что такое алгоритм сортировки кучи и как он работает, мы собираемся рассмотреть следующие концепции и структуры данных:
- Массивы
- Двоичные деревья
- Куча
- Двоичные кучи
Массивы
Структура данных Массив - это фундаментальная концепция, которая должна быть знакома каждому веб-разработчику на планете. Массивы будут использоваться не только на практике, но и в некоторой концептуальной роли, когда они будут реализованы в нашем HSA.
Обычно мы используем массив для хранения информации (в нашем случае целые числа). Обычно мы думаем о массивах как о списках данных с отдельными местами в памяти, к которым можно получить доступ напрямую (с помощью индексов) или с помощью циклов и встроенных методов.
В этом случае мы собираемся получить доступ к информации в массиве обычно но мы будем думать о его значениях как о элементах в двоичном дереве . С концептуальной точки зрения мы собираемся присвоить каждое значение определенному узлу дерева.
Бинарные деревья
Просто для быстрого освежения мы определим и объясним, что такое двоичные деревья.
Двоичное дерево: структура данных, которая начинается с корневого узла со значением и имеет (максимум) два дочерних узла, обычно называемых левым и правым узлами, которые имеют собственные ценности.
Двоичные деревья могут быть инициированы как объекты в JavaScript, которые выглядят следующим образом:
let tree = {
val: 2,
left: {
val: 3,
left: {
val: 4,
left: { ...},
right: { ...}
},
right: {
val: 5,
left: { ...},
right: { ...}
}
},
right: {
val: 7,
left: {
val: 8,
left: { ...},
right: { ...}
},
right: {
val: 9,
left: { ...},
right: { ...}
}
}
};
// The resulting binary tree would like this
2
/ \
3 7
/ \ / \
4 5 8 9
Хотя эта форма очень распространена, и вы можете реализовать двоичный поиск, чтобы перемещаться по ней и управлять ею, мы собираемся использовать массив для хранения значений нашего двоичного дерева вместо объекта. Вот иллюстрированный пример, чтобы прояснить, как массив будет представлять двоичное дерево в нашей реализации.
let array = [5,2,1,4,3];
// What the array represents as a binary tree structure
[5] 5
/ \
[2,1] 2 1
/ \
[4,3] 4 3
Важно отметить, что каждый горизонтальный слой дерева всегда располагается сверху вниз и слева направо и содержит два дочерних узла каждому родительскому (или корневому) узлу.
Используя подход, основанный на коде, мы можем определить, где находятся родительский и дочерний узлы в массиве, используя несколько простых формул. Мы можем начать с предположения, что начало массива (индекс 0, целое число 5) является корневым узлом.
let array = [5,2,1,4,3]; indexes --> [0,1,2,3,4] // parent node let p = (index - 1) / 2; // left child node let left = 2 * p + 1; // right child node let right = 2 * p + 2;
Куча / двоичная куча
Итак, мы определили, как массивы будут использоваться и концептуализированы в нашей реализации. Но что такое куча и как она связана с двоичным деревом?
Куча - это древовидная структура данных, которая соответствует критериям для одного из двух определений, приведенных ниже. А двоичная куча - это куча, которая приняла форму двоичного дерева, как определено выше.
Двоичное дерево с максимальной кучей: значение каждого родительского узла больше или равно его дочерним узлам.
15
/ \
12 18
/ \ / \
6 9 4 1
Двоичное дерево с минимальной кучей: значение каждого родительского узла меньше или равно его дочерним узлам.
3
/ \
8 5
/ \ / \
10 18 12 15
Как вы могли догадаться, конечной целью алгоритма сортировки кучи является сортировка списка значений с использованием максимальной или минимальной кучи . Единственное предостережение: двоичная куча может содержать братьев и сестер (дочерние узлы) со значениями, которые не соответствуют порядку (см. Примеры выше). Наша реализация должна будет это учитывать, чтобы не получить массив, который соответствует критериям для двоичной кучи но не для сортировки по возрастанию.
Реализации
Хорошо, мы закончили обзор, и, надеюсь, у вас есть достойное понимание структур данных и концепций, которые будут иметь отношение к нашим реализациям. Мы собираемся обрисовать в общих чертах две реализации (итеративную и рекурсивную) фактической функции Max Heap с пошаговым обзором всей базы кода.
Функция обмена
Мы собираемся разбить нашу кодовую базу на несколько разных функций, чтобы все было чисто и читабельно. Мы собираемся определить функцию подкачки, которая будет менять местами значения (на месте) в массиве. Мы будем повторно использовать эту функцию в наших реализациях.
const swap = (input, i, j) => {
const temp = input[i];
input[i] = input[j];
input[j] = temp;
};
Итеративная функция максимальной кучи
Итерационный подход практически идентичен рекурсивной реализации. Основное различие заключается в том, как функции повторяются в цикле или повторно инициализируются до тех пор, пока не будет выполнен базовый вариант. Вот краткое описание итеративной функции максимальной кучи:
- Инициализируйте цикл while, который будет продолжаться бесконечно, пока не сработает базовый случай.
- Инициализируйте 2 дочерних узла и максимальную переменную, которая отслеживает родительский индекс.
- Создайте 2 условных оператора, которые будут повторно назначать максимальное значение влево или вправо, если любой из дочерних индексов существует в пределах длины массива И значения в одном из этих массивов больше, чем значение в родительском / максимальном индексе
- Создайте базовый вариант, который выйдет из функции, когда родительский индекс НЕ был переназначен переменной max.
- Вызов функции подкачки с родительским индексом и обновленным максимальным индексом
- Назначьте родительский индекс (i) обновленной переменной max. Это эффективно обновляет родительский индекс до (того, что было) его самым большим дочерним узлом.
const iterativeMaxHeap = (array, i, length) => {
while (true) {
const left = 2 * i + 1;
const right = 2 * i + 2;
let max = i;
if (left < length && array[left] > array[max]) {
max = left
}
if (right < length && array[right] > array[max]) {
max = right
}
// Once this condition is met, exit the loop
if (i === max) {
break;
}
swap(array, i, max)
i = max;
}
};
Рекурсивная функция максимальной кучи
Это рекурсивная версия функции Max Heap.
- Инициализируйте цикл while, который будет продолжаться бесконечно, пока не сработает базовый случай.
- Инициализируйте 2 дочерних узла и максимальную переменную, которая отслеживает родительский индекс.
- Создайте 2 условных оператора, которые будут повторно назначать максимальное значение влево или вправо, если любой из дочерних индексов существует в пределах длины массива И значения в одном из этих массивов больше, чем значение в родительском / максимальном индексе
- Если значение переменной max изменилось, поменяйте местами родительский индекс с максимальным (левым или правым) индексом и снова вызовите функцию maxHeap.
const recursiveMaxHeap = (array, i, length) => {
const left = 2 * i + 1;
const right = 2 * i + 2;
let max = i;
if (left < length && array[left] > array[max]) {
max = left
}
if (right < length && array[right] > array[max]) {
max = right
}
if (i !== max) {
swap(array, i, max)
recursiveMaxHeap(array, max, length)
}
};
Функция Heapify
Эта функция создает допустимую кучу из входного массива. В этом случае мы создаем кучу Max внутри цикла, но мы могли бы создать кучу Min, если бы хотеть. Итеративная и рекурсивная реализации идентичны по своей форме. Вот простое пошаговое руководство:
- Мы инициализируем цикл, который начинается в середине массива и предназначен для перемещения назад к началу массива. Мы начинаем с середины, потому что maxHeap функция фактически создает кучу из первого индекса (или родительского узла) до последнего индекса (или дочернего узла). После каждого цикла мы эффективно перезаписываем родительские узлы любыми более крупными дочерними узлами, пока все это не станет допустимой кучей Max.
- Мы вызываем функцию maxHeap с массивом, текущим родительским индексом и длиной массива, который мы хотим поместить в кучу.
const heapify = (array) => {
for (let i = Math.floor(array.length / 2); i >= 0; i--) {
maxHeap(array, i, array.length)
}
};
Функция сортировки кучи
Это основная функция, которая движет всей нашей реализацией. Эта функция создает кучу из входного массива, а затем переупорядочивает массив (на месте) для создания отсортированного массива.
- Инициализируйте переменную len длиной входного массива.
- Создайте базовый вариант, который будет выходить из функции, если массив не имеет длины
- Мы вызываем heapify с массивом, чтобы преобразовать его в Max Heap
- Мы перебираем обновленный массив в обратном порядке и меняем местами целое число в конце массива на целое число в начале массива.
- Уменьшите переменную len на 1. Мы уменьшаем значение этой переменной после вызова функции swap, поскольку последний элемент наибольшее целое число в массиве, и мы можем считать его отсортированным. В следующем цикле он будет проигнорирован и не включен в вызовы swap или maxHeap.
- Вызовите функцию maxHeap с сокращенным значением len, чтобы сохранить массив в виде кучи после изменения значений массива .
const heapSort = (array) => {
let len = array.length;
// If the array doesn't have any values exit the function
if (!len) {
return;
}
heapify(array);
for (let i = array.length - 1; i > 0; i--) {
swap(array, 0, i)
len--
maxHeap(array, 0, len)
}
};
БАМ, у нас получилось! Это алгоритм сортировки кучи, реализованный в двух немного разных вариантах JavaScript. Вам может быть интересно, зачем кому-то использовать этот алгоритм сортировки вместо более простого решения? Как всегда, сложность времени и пространства являются важными элементами, которые следует учитывать при выборе одного алгоритма вместо другого.
Заключение
HSA изменяет массив на месте, что означает, что ему не требуется много памяти для работы. Но это также означает, что он изменяет ваш входной массив и фактически не возвращает ничего нового. Каждая функция использует ссылку на массив в памяти, когда они манипулируют его содержимым. В результате, если вы хотите увидеть отсортированный результат, вам придется console.log () массив после вызова heapSort , примерно так:
let array = [2,3,4,2,5,6,3,10]; heapSort(array) console.log(array) --> [2,2,3,3,4,5,6,10];
Эта функция нашей функции Сортировка кучи также означает, что она не совсем подходит для парадигмы функционального программирования, как для объектно-ориентированного подхода. Так что имейте это в виду, когда думаете о том, какой алгоритм сортировки использовать и как он впишется в ваше приложение.
HSA имеет временную сложность, равную O (n log n) в в лучшем случае и O (n) в худшем случае. Для сравнения с другими временными сложностями взгляните на эту диаграмму:
Чтобы получить полное представление о написанном нами коде и нескольких тестовых примерах, которые могут помочь вам полностью осмыслить алгоритм сортировки кучи, просмотрите мой Github Repo ниже:
Вот некоторые из источников, которые я использовал, чтобы узнать больше о сортировке в куче:
Статья в Википедии на удивление полезна -
Отличный взгляд на код, реализованный на некоторых других языках -
Вот и все! Спасибо за чтение.
