Как реализовать двоичную кучу в JavaScript в 2022 году?

Полное руководство по структуре данных двоичной кучи

Двоичная куча

Двоичная куча — это древовидная структура данных, которая имеет 2 свойства:

1. Это должно быть идеальное бинарное дерево (также известное как структурное свойство)
2. Каждый узел дерева должен быть либо ≥, либо ≤, чем оба его дочерних элемента. Другими словами, это должно быть либо Min heap, либо Max heap. (также известное как свойство кучи).

Идеальное бинарное дерево

Двоичное дерево, которое почти завершено, последний уровень дерева заполняется слева направо.

например, дерево, заданное в максимальной куче и минимальной куче, является примером идеального двоичного дерева.

Примечание: если вы еще не читали бинарное дерево, ознакомьтесь с ним

1. Как реализовать бинарное дерево в JavaScript?
2. Топ-5 основных проблем в бинарном дереве

Типы двоичной кучи

Двоичная куча бывает двух типов:

1. Макс куча
2. Минимальная куча

Макс куча

Двоичная куча, в которой каждый узел дерева ≥, чем оба его дочерних элемента. Таким образом, корень дерева будет максимальным среди всех узлов.

например, ниже дерево является примером кучи Max:

Минимальная куча

Двоичная куча, в которой каждый узел дерева меньше, чем оба его дочерних элемента. Таким образом, корень дерева будет минимальным среди всех узлов.

например, ниже дерево является примером минимальной кучи:

Представление двоичной кучи

Двоичная куча может быть представлена ​​списком узлов дерева, а также массивом. В этой статье мы сосредоточимся только на представлении двоичной кучи в виде массива.

Ключевые моменты, на которые следует обратить внимание, —

1. корень дерева Arr[0]
2. для любого индекса я,

Parent index = (i-1)/2
Left child index = 2 * i + 1
Right Child index = 2 * i + 2

Применение двоичной кучи

1. Сортировка кучей
2. Приоритетная очередь
3. Графовые алгоритмы (алгоритм Дейкстры — кратчайшего пути, Prims — MST)
4. Проблемы, когда вам нужно продолжать находить min после каждой итерации, например

а) К-й самый большой элемент в массиве

б) Планировщик заданий

в) Максимальное произведение 2 элементов в массиве

Это полный список — Проблемы кучи

Реализация двоичной минимальной кучи в JavaScript

‹script src=""https://gist.github.com/ajayv1/82bea3c569b80fc4c8cbb82b65505d7a.js"'›‹/script›

Использование (оба подхода приводят к допустимой двоичной минимальной куче)

Подход 1. Вставьте элементы массива один за другим в кучу. Функция кучи insert вызывает функцию heapifyUp внутри.

let pq = new PriorityQueue();
let arr = [80,70,40,20,10,60,50,30];
for (let i = 0; i < arr.length; i++) {
    pq.insert(arr[i]);
}
console.log('Heap using approach 1', pq);

Подход 2.Вставьте полные элементы массива в кучу (вызвав функцию build_heap). Функция кучи Build_heap вызывает функцию heapify, которая наполняет всю кучу.

let pr = new PriorityQueue();
pr.build_heap(arr);
console.log('Heap using approach 2', pr);

Результат

Реализация двоичной максимальной кучи в JavaScript

‹script src="https://gist.github.com/ajayv1/11fb38ca7c53e0979fcbcf14501684dc.js'›‹/script›

Использование (оба подхода дают правильную максимальную двоичную кучу)

Подход 1. Вставьте элементы массива один за другим в кучу. Функция кучи insert вызывает функцию heapifyUp внутри.

let pq = new BinaryMaxHeap();
let arr = [80,70,40,20,10,60,50,30];
for (let i = 0; i < arr.length; i++) {
    pq.insert(arr[i]);
}
console.log('Heap using approach 1', pq);

Подход 2.Вставьте полные элементы массива в кучу (вызвав функцию build_heap). Функция кучи Build_heap вызывает функцию heapify, которая наполняет всю кучу.

let pr = new BinaryMaxHeap();
pr.build_heap(arr);
console.log('Heap using approach 2', pr);

Результат

Краткое содержание

Существует множество практических проблем, которые легко решаются с помощью структуры данных двоичной кучи. Это необходимо для всех выпускников компьютерных наук.

Во многих языках программирования двоичная куча предоставляется изначально, но знание базовой реализации и создание пользовательской — это настоящее обучение.

Код в этой статье (написанный на JavaScript) можно импортировать на другие языки программирования по вашему выбору.

Попробуйте создать его на предпочитаемом вами языке программирования.

Для всех последних сообщений и статей, пожалуйста, посетите веб-сайт https://weekendtutorial.com/

Продолжайте учиться и будьте в безопасности.

Дополнительные материалы на PlainEnglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Подпишитесь на нас в Twitter и LinkedIn. Присоединяйтесь к нашему сообществу Discord.