Структура данных бинарной кучи Javascript

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

. min-heap свойство: значение каждого узла больше или равно значению его родителя, при этом элемент с минимальным значением находится в корне.
свойство max-heap свойство: значение каждого узла меньше или равно значению его родителя, при этом элемент с максимальным значением находится в корне.

let MinHeap = function() {
    let head = [null];
    this.insert = function(element) {
        head.push(element);
        if (head.length > 2) {
            let idx = head.length - 1;
            while (head[idx] < head[Math.floor(idx / 2)]) {
                if (idx >= 1) {
                    [head[Math.floor(idx / 2)], head[idx]] = [head[idx], head[Math.floor(idx / 2)]];
                    if (Math.floor(idx / 2) > 1) {
                        idx = Math.floor(idx / 2);
                    } else {
                        break;
                    }
                }
            }
        }
    }
}
let minHeap = new MinHeap();
minHeap.insert(2)
minHeap.insert(1)
minHeap.insert(3)
minHeap.insert(4)

let MaxHeap = function() {
    let head = [null];
    this.insert = function(element) {
        head.push(element);
        if (head.length > 2) {
            let idx = head.length - 1;
            while (head[idx] > head[Math.floor(idx / 2)]) {
                if (idx >= 1) {
                    [head[Math.floor(idx / 2)], head[idx]] = [head[idx], head[Math.floor(idx / 2)]];
                    if (Math.floor(idx / 2) > 1) {
                        idx = Math.floor(idx / 2);
                    } else {
                        break;
                    }
                }
            }
        }
    }
}
let maxHeap = new MaxHeap();
maxHeap.insert(2)
maxHeap.insert(1)
maxHeap.insert(3)
maxHeap.insert(4)

Вход в полноэкранный режим Выход из полноэкранного режима

Любые комментарии и предложения приветствуются.

Структура данных бинарной кучи Javascript

Рекомендуем почитать: