И как их реализовать в JavaScript
Вступление
Так что же такое куча? Куча - это просто очень специализированная версия структуры данных двоичного дерева. Помните, что основной характеристикой двоичного дерева является то, что каждый узел имеет ВСЕГО 2 дочерних элемента. Поэтому с каждым уровнем, на который вы спускаетесь по дереву, количество узлов удваивается.
Куча продвигает это определение на один шаг дальше, поскольку в дополнение к тому, что каждый узел имеет только 2 дочерних элемента, каждый родительский узел также должен быть больше (Max Heap) или меньше (Min Heap) каждого из своих 2 дочерних узлов. Назначение максимальной или минимальной кучи состоит в том, что она позволяет нам отслеживать максимальное или минимальное значение в наборе данных в режиме реального времени по мере добавления данных в структуру.
Где бы я мог использовать кучу?
Кучи чаще всего используются в реальном мире в так называемой очереди с приоритетом. Если вы знакомы со стандартной структурой данных очереди (если не я писал о ее реализации через связанный список здесь), вы поймете, что данные, добавляемые в очередь, следуют шаблону первым пришел - первым ушел (FIFO), где вещи удаляются в порядке добавления.
В очереди с приоритетом это не всегда так, поскольку некоторые элементы в очереди имеют более высокий приоритет, чем другие. На самом деле это гораздо более распространенная практика в реальном мире, чем простой список FIFO. Допустим, у вас есть несколько задач, которые нужно выполнить на работе. У вас есть список дел, в который вы добавляете каждую задачу как назначенную вам. Было бы неплохо, если бы вы могли просто работать над одной задачей за раз, вычеркивая каждую по мере добавления, пока вы не завершите список, однако это бывает редко.
Как часто вы бываете на работе и начинаете работать над одним делом, когда внезапно ваш босс вызывает вас и говорит: «Бросьте то, что вы делаете, у нас чрезвычайная ситуация, которая требует всего вашего внимания».
По сути, это и есть приоритетная очередь. Даже если у вас есть еще 7 пунктов в вашем списке дел, новая задача, которую дал вам начальник, внезапно приобретает приоритет над всеми остальными и перемещается прямо в начало списка.
Создание очереди приоритетов в JavaScript
Давайте придерживаться этого примера списка дел, где мы можем назначить приоритет каждому элементу в списке, чтобы он правильно упорядочивался в нашей очереди. Для этого мы будем использовать класс MinHeap, который мы создадим на JavasScript. Я выбрал MinHeap, потому что мы будем назначать элементам с наивысшим приоритетом 1, а с самым низким - 5. Вы можете легко использовать MaxHeap и просто перевернуть приоритеты, чтобы сделать большее число более высоким приоритетом.
Создание класса MinHeap
Мы начнем с определения класса MinHeap в файле, который я соответствующим образом назвал MinHeap.js.
Нам нужно создать функцию-конструктор, которая будет инициализировать наш класс каждый раз, когда мы вызываем «new MinHeap ()». Конструктор не будет принимать никаких параметров, но ему нужно будет создать атрибуты кучи и размера, которые мы инициализируем массивом, первый элемент которого имеет значение null и 0 соответственно. Это будет выглядеть так:
class MinHeap {
constructor() {
this.heap = [null];
this.size = 0;
}
}
Мы можем представить нашу кучу в виде двоичного дерева, и это будет то, чем она будет, но в этом сценарии мы просто будем использовать массив JavaScript для хранения фактических данных. Я объясню, как это работает, позже в этой статье.
Причина, по которой мы инициализируем первый элемент в массиве значением NULL, заключается в том, чтобы воспользоваться принципом работы индексации массива. Таким образом, минимальным элементом в нашем массиве всегда будет this.heap [1] вместо 0, а последним элементом всегда будет this.heap [this.size] вместо this.size-1. С таким проще работать.
Добавление в кучу
Далее нам понадобится способ добавления данных в нашу кучу. Мы сделаем это, создав такую функцию .add:
class MinHeap {
constructor() {
this.heap = [null];
this.size = 0;
}
add(value) {
this.heap.push(value);
this.size++;
}
}
Эта функция примет параметр «value» и использует встроенный метод .push для объектов массива JavaScript, чтобы добавить это значение в конец кучи. Мы также увеличим размер кучи на единицу.
Heapify Up
Теперь наши проницательные читатели могут сказать: «Подождите, если вы всегда просто добавляете данные в конец массива, как бы вы поддерживали порядок?» и это отличный момент.
Каждый раз, когда данные добавляются в нашу кучу (или удаляются из нее), нам нужно проверять, соблюдаются ли все условия кучи (у каждого родителя не более 2 дочерних элементов, а значение каждого родителя меньше, чем у каждого из дочерних элементов) .
Давайте рассмотрим это на примере. Создадим следующую кучу:
let heap = [null, 2, 4, 6]
В виде дерева он будет выглядеть так:
Теперь предположим, что мы используем наш метод добавления, чтобы добавить 3 в кучу.
heap.add(3)
Когда мы добавляем в кучу, мы нажимаем на конец массива кучи, и это будет выглядеть так:
heap = [null, 2, 4, 6, 3]
Или вот такое дерево:
Чтобы исправить это, нам нужно поменять местами родительский узел 4 и дочерний узел 3. Этот процесс восстановления состояния кучи называется Heapifying, и в случае, когда вы перемещаете узел вверх по дереву, пока он не окажется в правильный вид спорта это называется Heapigying Up (или Bubbling Up).
Давайте добавим вызов функции .heapifyUp в нашу функцию добавления.
class MinHeap {
constructor() {
this.heap = [null];
this.size = 0;
}
add(value) {
this.heap.push(value);
this.size++;
this.heapifyUp();
}
}
Нет, нам нужно определять heapify. Помните, что цель этой функции - проверить, не меньше ли вновь добавленный узел, чем значение его родительского узла. Если да, выполните замену. Затем мы повторяем этот процесс, пока узел не станет больше, чем его родительский узел.
Мы можем воссоздать это поведение, используя следующую функцию:
heapifyUp() {
let current = this.size;
while (current > 1 && this.heap[getParent(current)] > this.heap[current]) {
this.swap(current, getParent(current));
current = getParent(current);
}
}
Это большой дайджест, в котором используются еще несколько вспомогательных функций, которые мы разберем одну за другой.
Образцы левого и правого дочерних двоичных деревьев
Мы воспользуемся приятным шаблоном, который существует в двоичных деревьях, чтобы всегда иметь возможность захватывать левый дочерний узел, правый дочерний или родительский узел.
Сначала это может быть не интуитивно понятно, но из-за свойств двоичного дерева позиция индекса каждого дочернего элемента легко вычисляется на основе индукционной позиции родителей. Давайте взглянем:
Здесь узел со значением 3 находится в позиции индекса (красный), равного 2. Вы заметите, что его левый и правый дочерние элементы имеют индексы 4 и 5 соответственно.
Другой способ исправить это - расположить его дочерние элементы в позиции (parent_index * 2) слева и (parent_index * 2 + 1) справа. Пойдите и проверьте это также для 6-го узла. Модель верна.
И наоборот, если вы хотите найти индекс родительского узла, это всегда индекс узла, деленный на два, а затем округленный в меньшую сторону. Например, узел со значением 9 имеет индекс 6. Следовательно, его родительский узел будет в индексе 6/2 с округлением в меньшую сторону, так что 3. Для узла 13 это будет 7/2, что равно 3,5, округленное до 3. Таким образом, мы можем написать следующие функции для поиска любых узлов, дочерних или родительских узлов:
const getParent = current => Math.floor((current / 2)); const getLeft = current => current * 2; const getRight = current => current * 2 + 1;
Поменять местами
Другая вспомогательная функция, которая нам нужна, - это та, которая фактически выполняет подкачку, о которой мы упоминали ранее.
Мы назовем его .swap и можем реализовать его следующим образом:
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
Возвращаясь к Heapify Up
Теперь, если мы вернемся к нашей предыдущей функции heapify и добавим определение для наших новых функций, станет немного яснее, что происходит.
class MinHeap {
constructor() {
this.heap = [null];
this.size = 0;
}
add(value) {
this.heap.push(value);
this.size++;
this.bubbleUp();
}
heapifyUp() {
let current = this.size;
while (current > 1 && this.heap[getParent(current)] > this.heap[current]) {
this.swap(current, getParent(current));
current = getParent(current);
}
}
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
const getParent = current => Math.floor((current / 2));
const getLeft = current => current * 2;
const getRight = current => current * 2 + 1;
Мы используем getParent для перемещения вверх по куче, а затем меняем местами узлы, пока дочерний элемент меньше своего родителя.
Удалить минимальное значение
Пока это все хорошо, но весь смысл минимальной кучи заключается в том, чтобы иметь возможность возвращать корневое значение наверху, эффективно возвращая минимальное значение.
Для этого создадим еще одну функцию:
popMin() {
if (this.size === 0) {
return null
}
const min = this.heap[1];
this.heap[1] = this.heap[this.size];
this.size--;
this.heap.pop();
return min;
}
Если вы посмотрите на эту функцию, то заметите, что она меняет местами первый и последний элементы нашего массива кучи перед удалением минимума, который теперь является нашим последним значением. Это связано с тем, что если вы удалите корневой узел напрямую, у вас будет сломанное дерево с двумя узлами без родителей. Поскольку последний узел всегда бездетный, поменяв местами два перед удалением, вы избежите этой проблемы.
Однако теперь у вас другая проблема. Корневой узел больше не является минимальным. Нам нужно написать другую функцию, похожую на HeapifyUp, которая перемещает этот корневой узел вниз по дереву, пока он не окажется в нужном месте.
HeapifyDown
heapifyDown() {
let current = 1;
let leftChild = getLeft(current);
let rightChild = getRight(current);
// Check that there is something to swap (only need to check the left if both exist)
while (this.canSwap(current, leftChild, rightChild)){
// Only compare left & right if they both exist
if (this.exists(leftChild) && this.exists(rightChild)) {
// Make sure to swap with the smaller of the two children
if (this.heap[leftChild] < this.heap[rightChild]) {
this.swap(current, leftChild);
current = leftChild;
} else {
this.swap(current, rightChild);
current = rightChild;
}
} else {
// If only one child exist, always swap with the left
this.swap(current, leftChild);
current = leftChild;
}
leftChild = getLeft(current);
rightChild = getRight(current);
}
}
Эта функция полагается на другую вспомогательную функцию, чтобы проверить, возможен ли обмен, убедившись, что левый и правый дочерние элементы существуют, а затем путем выбора меньшего значения дочерних элементов и выполнения обмена.
Всегда выбирая меньшее из двух значений, вы гарантируете, что минимальное значение является родительским для двоичного дерева.
Вот две вспомогательные функции, которые вам понадобятся:
exists(index) {
return index <= this.size;
}
canSwap(current, leftChild, rightChild) {
// Check that one of the possible swap conditions exists
return (
this.exists(leftChild) && this.heap[current] > this.heap[leftChild]
|| this.exists(rightChild) && this.heap[current] > this.heap[rightChild]
);
}
Теперь давайте добавим heapifyDown к нашей функции popMin:
popMin() {
if (this.size === 0) {
return null
}
const min = this.heap[1];
this.heap[1] = this.heap[this.size];
this.size--;
this.heap.pop();
this.heapifyDown();
return min;
}
Вот и все! Наш последний класс MinHeap приведен ниже:
class MinHeap {
constructor() {
this.heap = [null];
this.size = 0;
}
add(value) {
this.heap.push(value);
this.size++;
this.bubbleUp();
}
popMin() {
if (this.size === 0) {
return null
}
const min = this.heap[1];
this.heap[1] = this.heap[this.size];
this.size--;
this.heap.pop();
this.heapify();
return min;
}
heapifyUp() {
let current = this.size;
while (current > 1 && this.heap[getParent(current)] > this.heap[current]) {
this.swap(current, getParent(current));
current = getParent(current);
}
}
heapifyDown() {
let current = 1;
let leftChild = getLeft(current);
let rightChild = getRight(current);
while (this.canSwap(current, leftChild, rightChild)){
if (this.exists(leftChild) && this.exists(rightChild)) {
if (this.heap[leftChild] < this.heap[rightChild]) {
this.swap(current, leftChild);
current = leftChild;
} else {
this.swap(current, rightChild);
current = rightChild;
}
} else {
this.swap(current, leftChild);
current = leftChild;
}
leftChild = getLeft(current);
rightChild = getRight(current);
}
}
swap(a, b) {
[this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
}
exists(index) {
return index <= this.size;
}
canSwap(current, leftChild, rightChild) {
return (
this.exists(leftChild) && this.heap[current] > this.heap[leftChild]
|| this.exists(rightChild) && this.heap[current] > this.heap[rightChild]
);
}
}
const getParent = current => Math.floor((current / 2));
const getLeft = current => current * 2;
const getRight = current => current * 2 + 1;
