Это 90-я оригинальная статья без воды. Если вы хотите получить больше оригинальных статей, выполните поиск в публичном аккаунте и подпишитесь на нас~ Эта статья была впервые опубликована в блоге Zhengcaiyun:Как реализовать бинарную кучу с помощью JS
Как реализовать бинарную кучу с помощью JS
предисловие
Двоичное дерево представляет собой древовидную структуру, и его характеристика состоит в том, что каждый узел имеет не более двух узлов ветвления.Двоичное дерево обычно состоит из корневого узла, узла ветвления и конечного узла, как показано на следующем рисунке. Каждый узел ветвления также часто называют поддеревом, а двоичная куча — это особый вид дерева, принадлежащий полному двоичному дереву.
Связь между бинарным деревом и бинарной кучей
В повседневной работе возникает множество операций над массивами, например, сортировка. Тогда понимание реализации двоичной кучи повысит эффективность разработки в будущем.Ниже приводится краткое введение в то, что такое двоичное дерево и что такое двоичная куча.
Особенности бинарного дерева
- Корневой узел: самый верхний узел бинарного дерева.
- Узел ответвления: в дополнение к корневому узлу и имеет конечные узлы.
- Листовой узел: никаких других дочерних узлов, кроме самого себя
В бинарных деревьях мы часто используем родительские узлы и дочерние узлы для их описания.Например, левый узел 2 на приведенном выше рисунке является родительским узлом 6 и 3, и наоборот, 6 и 3 являются двумя дочерними узлами.
Классификация бинарного дерева
Бинарное дерево делится на полное бинарное дерево (fullbinarytree) и полное бинарное дерево (completebinarytree).
- Полное бинарное дерево: бинарное дерево с глубиной k и 2 ^ k - 1 узлами называется полным бинарным деревом.
- Полное двоичное дерево: полное двоичное дерево - последний слева заполнен, полный справа, также может быть недоволен, то остальные слои являются полным двоичным деревом, называемым полным двоичным деревом (также полное двоичное дерево.
бинарная древовидная структура
Из рисунка видно, что бинарное дерево упорядочено сверху вниз.Можно предположить, что для представления структуры бинарного дерева можно использовать массив, который упорядочен сверху вниз от индекса индекса ( 0 - 8).
- Выражением узла в левой части бинарного дерева является index * 2 + 1. Например: взять в качестве примера корневой узел, чтобы найти левый узел, нижний индекс корневого узла равен 0, тогда порядковый номер левого узла равен 1, а значение в соответствующем массиве равно 1.
- Выражением узла в правой части бинарного дерева является index * 2 + 2. Например: взять в качестве примера корневой узел, чтобы найти правильный узел, нижний индекс корневого узла равен 0, тогда порядковый номер правого узла равен 2, а соответствующее значение в массиве равно 8.
- Выражение листового узла бинарного дерева Ordinal >= floor( N / 2 ) — листовые узлы (N — длина массива). Например: floor( 9 / 2 ) = 4 , тогда значения, начинающиеся с нижнего индекса 4, являются листовыми узлами
Функции двоичной кучи
Двоичная куча — это полное двоичное дерево.Родительский узел и дочерние узлы должны поддерживать отношения фиксированного порядка, а левое и правое поддеревья каждого узла представляют собой двоичную кучу.
Как видно из приведенного выше рисунка
- Рис. 1. Каждый родительский узел больше или равен дочернему узлу, который удовлетворяет свойствам двоичной кучи
- Рис. 2. Если один родительский узел меньше дочернего, свойство двоичной кучи не выполняется.
Классификация двоичной кучи
Двоичная куча может быть разделена на максимальную кучу и минимальную кучу в соответствии с различной сортировкой.
- Максимальная куча: значение ключа корневого узла является наибольшим из всех значений ключа узла кучи, а значение каждого родительского узла больше, чем значение дочернего узла.
- Минимальная куча: значение ключа корневого узла является наименьшим из всех значений ключа узла кучи, а значение каждого родительского узла меньше значения дочернего узла.
Как реализовать бинарную кучу
Благодаря приведенному выше описанию каждый должен иметь определенное представление о двоичной куче, тогда следующим шагом будет ее реализация. Взяв в качестве примера максимальную кучу, массив сначала инициализируется, а затем формируется максимальная куча путем замены позиций.
Инициализировать двоичную кучу
Из приведенного выше описания мы можем узнать, что двоичная куча на самом деле является массивом, поэтому инициализация очень проста.
class Heap{
constructor(arr){
this.data = [...arr];
this.size = this.data.length;
}
}
родительский и дочерний узлы меняются местами
На рис. 1, 2 родительский узел меньше дочернего, что явно не соответствует свойству максимальной кучи. Функция maxHeapify может изменить положение каждого узла, который не соответствует максимальным свойствам кучи, чтобы удовлетворить максимальные свойства кучи массива.
Шаги регулировки:
1. корректировка положения узлов ветвления 2 (не удовлетворяет свойству максимальной кучи)
2. Получите левый и правый узлы родительского узла 2 (12, 5) и сравните их с (2, 15, 5)
3. Найдите самый большой узел для обмена с родительским узлом и остановите операцию, если сам узел является самым большим узлом.
4. Повторите операцию шага 2, найдите максимальное значение из 2, 4, 7 и замените его на 2 (рекурсия)
maxHeapify(i) {
let max = i;
if(i >= this.size){
return;
}
// 当前序号的左节点
const l = i * 2 + 1;
// 当前需要的右节点
const r = i * 2 + 2;
// 求当前节点与其左右节点三者中的最大值
if(l < this.size && this.data[l] > this.data[max]){
max = l;
}
if(r < this.size && this.data[r] > this.data[max]){
max = r;
}
// 最终max节点是其本身,则已经满足最大堆性质，停止操作
if(max === i) {
return;
}
// 父节点与最大值节点做交换
const t = this.data[i];
this.data[i] = this.data[max];
this.data[max] = t;
// 递归向下继续执行
return this.maxHeapify(max);
}
сформировать максимальную кучу
Мы видим, что инициализация состоит из массива.Очевидно, что следующий рисунок не удовлетворяет свойству максимальной кучи.Приведенная выше функция maxHeapify только меняет местами определенный узел и не может реконструировать весь массив, поэтому мы должны следовать последовательность Рекурсивно реконструировать массив.
1. Найдите все узлы ветвления Math.floor( N / 2 ) (исключая листовые узлы)
2. Были найдены дочерние узлы операции maxHeapify
rebuildHeap(){
// 叶子节点
const L = Math.floor(this.size / 2);
for(let i = L - 1; i >= 0; i--){
this.maxHeapify(i);
}
}
генерировать возрастающий массив
1. Функция подкачки меняет местами первую позицию
2. Берём из кучи последний, равный размеру - 1
3. Выполните функцию maxHeapify, чтобы сравнить корневые узлы и найти максимальное значение для обмена.
4. В конце концов данные станут массивом в порядке возрастания
sort() {
for(let i = this.size - 1; i > 0; i--){
swap(this.data, 0, i);
this.size--;
this.maxHeapify(0);
}
}
Метод вставки
Вставить функцию как функцию вставки узла, сначала
1. Вставьте узел в конец данных
2. Поскольку узел добавлен, размер + 1
3. Поскольку родительский узел имеет 2 дочерних узла, мы можем получить первый листовой узел через функцию isHeap в соответствии с этим свойством и получить вновь вставленный узел через первый листовой узел, а затем сравнить три значения, чтобы найти максимальное значение.значение, чтобы определить вставленный узел. Если он совпадает с родительским узлом, реконструкция выполняться не будет (равенство удовлетворяет свойству бинарной кучи), в противном случае для восстановления кучи будет выполняться rebootHeap.
isHeap() {
const L = Math.floor(this.size / 2);
for (let i = L - 1; i >= 0; i--) {
const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;
const max = Math.max(this.data[i], l, r);
if (max !== this.data[i]) {
return false;
}
return true;
}
}
insert(key) {
this.data[this.size] = key;
this.size++
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}
метод удаления
удалить функцию как удалить узел, сначала
1. Удалить узел входящего индекса
2. Поскольку узел удален, размер - 1
3. Повторите описанную выше операцию вставки узлов.
delete(index) {
if (index >= this.size) {
return;
}
this.data.splice(index, 1);
this.size--;
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}
полный код
/**
* 最大堆
*/
function left(i) {
return (i * 2) + 1;
}
function right(i) {
return (i * 2) + 2;
}
function swap(A, i, j) {
const t = A[i];
A[i] = A[j];
A[j] = t;
}
class Heap {
constructor(arr) {
this.data = [...arr];
this.size = this.data.length;
this.rebuildHeap = this.rebuildHeap.bind(this);
this.isHeap = this.isHeap.bind(this);
this.sort = this.sort.bind(this);
this.insert = this.insert.bind(this);
this.delete = this.delete.bind(this);
this.maxHeapify = this.maxHeapify.bind(this);
}
/**
* 重构堆，形成最大堆
*/
rebuildHeap() {
const L = Math.floor(this.size / 2);
for (let i = L - 1; i >= 0; i--) {
this.maxHeapify(i);
}
}
isHeap() {
const L = Math.floor(this.size / 2);
for (let i = L - 1; i >= 0; i--) {
const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;
const max = Math.max(this.data[i], l, r);
if (max !== this.data[i]) {
return false;
}
return true;
}
}
sort() {
for (let i = this.size - 1; i > 0; i--) {
swap(this.data, 0, i);
this.size--;
this.maxHeapify(0);
}
}
insert(key) {
this.data[this.size++] = key;
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}
delete(index) {
if (index >= this.size) {
return;
}
this.data.splice(index, 1);
this.size--;
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}
/**
* 交换父子节点位置，符合最大堆特征
* @param {*} i
*/
maxHeapify(i) {
let max = i;
if (i >= this.size) {
return;
}
// 求左右节点中较大的序号
const l = left(i);
const r = right(i);
if (l < this.size && this.data[l] > this.data[max]) {
max = l;
}
if (r < this.size && this.data[r] > this.data[max]) {
max = r;
}
// 如果当前节点最大，已经是最大堆
if (max === i) {
return;
}
swap(this.data, i, max);
// 递归向下继续执行
return this.maxHeapify(max);
}
}
module.exports = Heap;
Пример
Я считаю, что у всех есть определенное понимание реализации максимальной кучи через приведенное выше описание, и мы можем использовать это для сортировки.
const arr = [15, 12, 8, 2, 5, 2, 3, 4, 7];
const fun = new Heap(arr);
fun.rebuildHeap(); // 形成最大堆的结构
fun.sort();// 通过排序，生成一个升序的数组
console.log(fun.data) // [2, 2, 3, 4, 5, 7, 8, 12, 15]
Суммировать
В статье в основном описываются концепции двоичного дерева и двоичной кучи, а затем реализуется двоичная куча с помощью кода. Мы можем делать сортировку и приоритеты очередей через бинарные кучи.
Рекомендуемое чтение
Фронтенд-захват и обработка исключений
Написание высококачественного поддерживаемого кода: абстракция компонентов и гранулярность
Карьера
ZooTeam, молодая, увлеченная и творческая команда, связанная с отделом исследований и разработок продукции Zhengcaiyun, базируется в живописном Ханчжоу. В настоящее время в команде более 40 фронтенд-партнеров, средний возраст которых составляет 27 лет, и почти 30% из них — инженеры полного стека, настоящая молодежная штурмовая группа. В состав членов входят «ветераны» солдат из Ali и NetEase, а также первокурсники из Чжэцзянского университета, Университета науки и технологий Китая, Университета Хандянь и других школ. В дополнение к ежедневным деловым связям, команда также проводит технические исследования и фактические боевые действия в области системы материалов, инженерной платформы, строительной платформы, производительности, облачных приложений, анализа и визуализации данных, а также продвигает и внедряет ряд внутренних технологий. Откройте для себя новые горизонты передовых технологических систем.
Если вы хотите измениться, вас забрасывают вещами, и вы надеетесь начать их бросать; если вы хотите измениться, вам сказали, что вам нужно больше идей, но вы не можете сломать игру; если вы хотите изменить , у вас есть возможность добиться этого результата, но вы не нужны; если вы хотите изменить то, чего хотите достичь, вам нужна команда для поддержки, но вам некуда вести людей; если вы хотите изменить установившийся ритм, это будет "5 лет рабочего времени и 3 года стажа работы"; если вы хотите изменить исходный Понимание хорошее, но всегда есть размытие того слоя оконной бумаги.. , Если вы верите в силу веры, верьте, что обычные люди могут достичь необыкновенных вещей, и верьте, что они могут встретить лучшего себя. Если вы хотите участвовать в процессе становления бизнеса и лично способствовать росту фронтенд-команды с глубоким пониманием бизнеса, надежной технической системой, технологиями, создающими ценность, и побочным влиянием, я думаю, что мы должны говорить. В любое время, ожидая, пока вы что-нибудь напишете, отправьте это наZooTeam@cai-inc.com