Структуры данных важны в компьютерном программировании для быстрой и эффективной организации, управления и хранения данных. Структуры данных — это абсолютно необходимый навык для любого разработчика, который должен быть в его наборе инструментов.
Сегодня мы продолжим серию статей «Структуры данных 101», сосредоточив внимание на Heaps, специальной древовидной структуре данных, реализующей полное двоичное дерево.
Сегодня мы рассмотрим:
- Что такое куча?
- Основные операции в кучах
- Как построить максимальную кучу
- Как построить мини-кучу
- Вызов кучи: практическая практика
- Что изучать дальше
Что такое куча?
Куча — это расширенная древовидная структура данных, используемая в основном для сортировки и реализации приоритетных очередей. Это полные бинарные деревья, которые имеют следующие особенности:
- Каждый уровень заполнен, кроме листовых узлов (узлы без дочерних элементов называются листьями).
- Каждый узел имеет максимум 2 дочерних узла.
- Все узлы максимально левые. Это означает, что каждый ребенок находится слева от своего родителя.
Кучи используют полные двоичные деревья, чтобы избежать дыр в массиве. Полное бинарное дерево — это дерево, в котором каждый узел имеет не более двух дочерних элементов, а узлы на всех уровнях заполнены, за исключением конечных узлов, которые могут быть пустыми. Кучи строятся на основе свойства кучи, которое сравнивает ключ родительского узла с ключами дочернего узла.
Важно отметить, что кучи не всегда сортируются. Ключевое условие, которому они следуют, заключается в том, что самый большой или самый маленький элемент помещается в корневой узел (сверху) в зависимости от того, является ли он максимальной или минимальной кучей. Структура данных кучи отличается от кучи памяти.
Плюсы и минусы кучи
Плюсы:
- Сборка мусора выполняется в памяти кучи, чтобы освободить память, используемую объектом.
- Кучи являются гибкими, так как память может быть выделена или удалена в любом порядке.
- Доступ к переменным возможен глобально.
- Это помогает найти минимальное и наибольшее число.
Минусы:
- По сравнению со стеками кучи требуют больше времени для выполнения.
- Управление памятью в куче сложнее, так как она используется глобально.
- Кучи обычно требуют больше времени для вычисления.
Приложения структуры данных кучи
Кучи эффективны для поиска минимального или максимального элемента в массиве и полезны для статистики порядка и алгоритмов выбора. Временная сложность получения минимального/максимального значения из кучи составляет O(1) (постоянная временная сложность).
Очереди с приоритетом разработаны на основе структур кучи. Эффективная вставка (insert()) и удаление (delete()) каждого элемента в очереди приоритетов занимает O(log(n)) времени.
Очереди с приоритетами, реализованные в куче, используются в популярных алгоритмах, таких как:
- Алгоритм Прима
- Алгоритм Дейкстры
- Алгоритм Heapsort
Основные операции в кучах
Ниже приведены основные операции, которые вы можете использовать при реализации структуры данных кучи:
heapify: переупорядочивает элементы в куче, чтобы сохранить свойство кучи.insert: добавляет элемент в кучу, сохраняя его свойство кучи.delete: удаляет элемент в куче.extract: возвращает значение элемента, а затем удаляет его из кучи.isEmpty: логическое значение, возвращает true, если логическое значение пусто, и false, если оно имеет узел.size: возвращает размер кучи.getMax(): возвращает максимальное значение в куче
Как построить максимальную кучу
Элементы в максимальной куче следуют свойству максимальной кучи. Это означает, что ключ в родительском узле всегда больше, чем ключ в обоих дочерних узлах. Чтобы создать максимальную кучу:
- Создайте новый узел в начале (корне) кучи.
- Присвойте ему значение.
- Сравните значение дочернего узла с родительским узлом.
- Поменять местами узлы, если значение родителя меньше, чем значение любого дочернего элемента (слева или справа).
- Повторяйте до тех пор, пока самый большой элемент не окажется в корневом родительском узле (тогда вы можете сказать, что свойство кучи выполняется).
Эти шаги также можно выполнить при вставке новых элементов в кучу. Ключевым моментом здесь является то, что какая бы операция ни выполнялась с максимальной кучей, свойство кучи должно поддерживаться.
Чтобы удалить/удалить корневой узел в Max Heap:
- Удалить корневой узел.
- Переместите последний дочерний узел последнего уровня в корень.
- Сравните родительский узел с его дочерними элементами.
- Если значение родительского узла меньше, чем значение дочерних узлов, поменяйте их местами и повторяйте, пока не будет удовлетворено свойство кучи.
Давайте посмотрим, как это выглядит в коде. В следующем разделе мы реализуем максимальную кучу с помощью JavaScript.
Реализация Max Heap в JavaScript
Прежде чем мы приступим к созданию Max Heap, взгляните на некоторые методы, которые мы реализуем, и на то, что они делают:
_percolateUp(): восстанавливает свойство кучи из дочернего узла в корневой узел._maxHeapify(): восстанавливает свойство кучи с определенного узла до конечных узлов.insert(): добавляет заданное значение в массив кучи и переупорядочивает элементы на основе их свойства кучи. При каждой новой вставке куча равномерно растет, а размер увеличивается на единицу.getMax(): возвращает максимальное значение в куче (корневой узел) без изменения кучи. Обратите внимание, что временная сложность здесь — постоянное время O(1)removeMax(): возвращает и удаляет максимальное значение в куче (подумайте оpop()). Временная сложность этой функции составляет O(log(n)).
Если размер кучи больше единицы, он сохраняет максимальное значение в переменной, заменяет это значение последним листом и удаляет максимальное значение из кучи.
Если в куче есть только один элемент, он удаляет и возвращает значение этого элемента. Последнее условие: если куча пуста, возвращается значение null.
Метод __percolateUp() вызывается рекурсивно на каждом родительском узле, пока не будет достигнут корень. Чтобы каждый узел располагался после свойства max-heap, мы вызываем метод __maxHeapify() для каждого индекса этого массива, начиная с нижней части кучи.
class maxHeap {
constructor() {
this.heap = [];
this.elements = 0;
};
insert(val) {
if (this.elements >= this.heap.length) {
this.elements = this.elements + 1;
this.heap.push(val);
this.__percolateUp(this.heap.length - 1);
}
else {
this.heap[this.elements] = val;
this.elements = this.elements + 1;
this.__percolateUp(this.elements - 1);
}
};
getMax() {
if (this.elements !== 0)
return this.heap[0];
return null;
};
removeMax() {
let max = this.heap[0];
if (this.elements > 1) {
this.heap[0] = this.heap[this.elements - 1];
this.elements = this.elements - 1;
this.__maxHeapify(0);
return max
} else if (this.elements === 1) {
this.elements = this.elements - 1;
return max;
} else {
return null;
}
};
__percolateUp(index) {
const parent = Math.floor((index - 1) / 2);
if (index <= 0)
return
else if (this.heap[parent] < this.heap[index]) {
let tmp = this.heap[parent];
this.heap[parent] = this.heap[index];
this.heap[index] = tmp;
this.__percolateUp(parent);
}
};
__maxHeapify(index) {
let left = (index * 2) + 1;
let right = (index * 2) + 2;
let largest = index;
if ((this.elements > left) && (this.heap[largest] < this.heap[left])) {
largest = left
}
else if ((this.elements > right) && (this.heap[largest] < this.heap[right]))
largest = right
else if (largest !== index) {
const tmp = this.heap[largest];
this.heap[largest] = this.heap[index];
this.heap[index] = tmp;
this.__maxHeapify(largest);
}
};
buildHeap(arr) {
this.heap = arr;
this.elements = this.heap.length;
for (let i = this.heap.length - 1; i >= 0; i--) {
this.__maxHeapify(i);
}
};
};
let heap = new maxHeap();
Как построить минимальную кучу
Интуитивно мы можем сказать, что элементы в минимальной куче следуют свойству минимальной кучи, так как это противоположно максимальным кучам. Ключ родительского узла всегда меньше ключа обоих дочерних узлов. Чтобы создать мини-кучу:
- Создайте новый дочерний узел в конце кучи (последний уровень).
- Добавьте новый ключ к этому узлу (добавьте его в массив).
- Переместите дочерний элемент вверх, пока не достигнете корневого узла и не будет удовлетворено свойство кучи.
Чтобы удалить/удалить корневой узел в минимальной куче:
- Удалить корневой узел.
- Переместите ключ последнего потомка в корень.
- Сравните родительский узел с его дочерними элементами.
- Если значение родительского узла больше, чем значение дочерних узлов, поменяйте их местами и повторяйте, пока не будет удовлетворено свойство кучи.
Реализация минимальной кучи в JavaScript
Прежде чем мы приступим к созданию минимальной кучи, обратите внимание, что ее реализация аналогична реализации Max Heap. minHeapify() восстанавливает свойство кучи. getMin() возвращает минимальное значение в куче (корневой узел) без изменения кучи. А removeMin() удаляет минимальное значение и возвращает его.
class minHeap {
constructor() {
this.heap = []
this.elements = 0;
};
insert(val) {
if (this.elements >== this.heap.length) {
this.elements = this.elements + 1
this.heap.push(val);
this.__percolateUp(this.heap.length - 1);
}
else {
this.heap[this.elements] = val;
this.elements = this.elements + 1;
this.__percolateUp(this.elements - 1);
}
};
getMin() {
if (this.heap.length !== 0)
return this.heap[0];
return null;
}
removeMin() {
const min = this.heap[0];
if (this.elements > 1) {
this.heap[0] = this.heap[this.elements - 1];
this.elements = this.elements - 1;
this.__minHeapify(0);
return min;
} else if (this.elements == 1) {
this.elements = this.elements - 1;
return min;
} else {
return null;
}
};
__percolateUp(index) {
let parent = Math.floor((index - 1) / 2);
if (index <= 0)
return
else if (this.heap[parent] > this.heap[index]) {
let tmp = this.heap[parent];
this.heap[parent] = this.heap[index];
this.heap[index] = tmp;
this.__percolateUp(parent);
}
};
__minHeapify(index) {
let left = (index * 2) + 1;
let right = (index * 2) + 2;
let smallest = index;
if ((this.elements > left) && (this.heap[smallest] > this.heap[left])) {
smallest = left;
}
if ((this.elements > right) && (this.heap[smallest] > this.heap[right]))
smallest = right;
if (smallest !== index) {
let tmp = this.heap[smallest];
this.heap[smallest] = this.heap[index];
this.heap[index] = tmp;
this.__minHeapify(smallest);
}
}
buildHeap(arr) {
this.heap = arr;
this.elements = this.heap.length;
for (let i = this.heap.length - 1; i >= 0; i--) {
this.__minHeapify(i)
}
}
};
let heap = new minHeap();
heap.insert(12);
heap.insert(10);
heap.insert(-10);
heap.insert(100);
console.log(heap.getMin()); //you should get -10
let newheap = new minHeap();
let arr = [12, 6, 8, 3, 16, 4, 27];
newheap.buildHeap(arr) //builds this new heap with elements from the array
console.log(newheap.getMin()) //this logs 3
newheap.removeMin();
console.log(newheap.getMin())
Задача кучи: преобразовать максимальную кучу в минимальную кучу
Давайте продвинемся в нашем обучении еще на один шаг, приняв практическое задание. Наша цель здесь — преобразовать максимальную кучу в минимальную. Следуйте вместе с нашим кодовым решением, чтобы увидеть, как это делается.
Постановка задачи. Реализуйте функцию convertMax(maxHeap), которая будет преобразовывать двоичную максимальную кучу в двоичную минимальную кучу, где maxHeap – это массив в формате maxHeap (т. е. родительский массив больше, чем его дочерние элементы). Ваш вывод должен быть преобразованным массивом.
Пример ввода:
maxHeap = [9,4,7,1,-2,6,5]
Пример вывода:
result = [-2,1,5,9,4,6,7]
Проблема:
function convertMax(maxHeap) {
return maxHeap
}
Решение:
function minHeapify(heap, index) {
var left = index * 2;
var right = (index * 2) + 1;
var smallest = index;
if ((heap.length > left) && (heap[smallest] > heap[left])) {
smallest = left
}
if ((heap.length > right) && (heap[smallest] > heap[right]))
smallest = right
if (smallest != index) {
var tmp = heap[smallest]
heap[smallest] = heap[index]
heap[index] = tmp
minHeapify(heap, smallest)
}
return heap;
}
function convertMax(maxHeap) {
for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
maxHeap = minHeapify(maxHeap, i)
return maxHeap
}
Приведенное выше кодовое решение можно запустить. Мы можем рассматривать данный maxHeap как обычный массив элементов и переупорядочить его так, чтобы он точно представлял минимальную кучу. Функция convertMax() восстанавливает свойство кучи на всех узлах из самого нижнего родительского узла, вызывая функцию minHeapify() на каждом.
Временная сложность построения кучи составляетO(n). Это относится и к этой проблеме.
function minHeapify(heap, index) {
var left = index * 2;
var right = (index * 2) + 1;
var smallest = index;
if ((heap.length > left) && (heap[smallest] > heap[left])) {
smallest = left
}
if ((heap.length > right) && (heap[smallest] > heap[right]))
smallest = right
if (smallest != index) {
var tmp = heap[smallest]
heap[smallest] = heap[index]
heap[index] = tmp
minHeapify(heap, smallest)
}
return heap;
}
function convertMax(maxHeap) {
for (var i = Math.floor((maxHeap.length) / 2); i > -1; i--)
maxHeap = minHeapify(maxHeap, i)
return maxHeap
}
var maxHeap = [9,4,7,1,-2,6,5]
console.log(convertMax(maxHeap))
-->
[ -2, 1, 4, 5, 7, 6, 9 ]
Что изучать дальше
Поздравляем, вы добрались до конца этой статьи. Я надеюсь, что теперь вы хорошо знаете, как работают кучи, и можете уверенно создавать кучи с помощью JavaScript.
Вот несколько общих задач, которые помогут проверить ваши знания о структуре данных кучи. Вы можете ожидать увидеть эти вопросы в интервью по программированию:
- Преобразовать максимальную кучу в минимальную кучу
- Найти k наименьший элемент в массиве
- Найти k самый большой элемент в массиве
- Проверьте, представляет ли данный массив минимальную кучу или нет
- Объединить M-отсортированные списки переменной длины
- Найдите наименьший диапазон, содержащий хотя бы один элемент из каждого из заданных списков.
Чтобы найти ответы на эти вопросы и продолжить обучение, ознакомьтесь с курсом Educative Структуры данных для интервью по кодированию в JavaScript. Он даст вам подробное объяснение всех распространенных структур данных JavaScript с решениями реальных проблем со структурами данных. Вы будете хорошо оснащены всеми различными структурами данных, которые вы используете для написания лучшего кода.
Удачного обучения!
Продолжить чтение о JavaScript и структурах данных на Educative
- Лучшие структуры данных и алгоритмы, которые должен знать каждый разработчик
- Учебник по JavaScript Snake Game: создайте простую интерактивную игру
- Шпаргалка по нотации Big-O: быстрые ответы на вопросы Big-O
Начать обсуждение
С какой структурой данных JavaScript вам больше всего нравится работать? Была ли эта статья полезна? Дайте нам знать в комментариях ниже!
