Минимальная Heap в JavaScript

Min -Heap — это полное двоичное дерево, в котором значение в каждом внутреннем узле меньше или равно значениям в дочерних элементах этого узла. Отображение элементов кучи в массив тривиально: если узел хранится с индексом k, то его левый дочерний элемент хранится с индексом 2k + 1, а его правый дочерний элемент — с индексом 2k + 2.

Как представлена ​​Min Heap?

Пройдемся по представлению кучи Min. Итак, в основном Min Heap — это полное двоичное дерево. Куча Min обычно представляется в виде массива. Корневой элемент будет в Arr[0]. Для любого i-го узла, т. е. Arr[i]

• Arr[(i −1)/2]возвращает родительский узел.
• Arr[(2 * i) + 1]возвращает левый дочерний узел.
• Arr[(2 * i) + 2]возвращает правый дочерний узел.

Операции структуры данных Heap:

• Heapify: процесс создания кучи из массива.
• Вставка: процесс для вставки элемента в существующую временную сложность кучи O (log N).
• Удаление: удаление верхнего элемента кучи или элемента с наивысшим приоритетом, а затем организация кучи и возврат элемента с временной сложностью O (log N).
• Peek: чтобы проверить или найти самый ранний элемент в куче (максимальный или минимальный элемент для максимальной и минимальной кучи).

Объяснение: Теперь давайте разберемся, как различные вспомогательные методы поддерживают порядок в куче.

• Вспомогательные методы, такие как rightChild, leftChild и parent,помогают нам получить элемент и его дочерние элементы по указанному индексу.
• Методы add ()и remove() обрабатывают процесс вставки и удаления.
• Метод heapifyDown ()поддерживает структуру кучи при удалении элемента.
• Метод heapifyUp()поддерживает структуру кучи, когда в нее добавляется элемент.
• Метод peek() возвращает корневой элемент кучи, а метод swap() обменивает значения в двух узлах.

Пример. В этом примере мы реализуем структуру данных Min Heap.

Javascript

class MinHeap {

    constructor() {

        this.heap = [];

    }

 

    // Helper Methods

    getLeftChildIndex(parentIndex) {

        return 2 * parentIndex + 1;

    }

    getRightChildIndex(parentIndex) {

        return 2 * parentIndex + 2;

    }

    getParentIndex(childIndex) {

        return Math.floor((childIndex - 1) / 2);

    }

    hasLeftChild(index) {

        return this.getLeftChildIndex(index) < this.heap.length;

    }

    hasRightChild(index) {

        return this.getRightChildIndex(index) < this.heap.length;

    }

    hasParent(index) {

        return this.getParentIndex(index) >= 0;

    }

    leftChild(index) {

        return this.heap[this.getLeftChildIndex(index)];

    }

    rightChild(index) {

        return this.heap[this.getRightChildIndex(index)];

    }

    parent(index) {

        return this.heap[this.getParentIndex(index)];

    }

 

    // Functions to create Min Heap

     

    swap(indexOne, indexTwo) {

        const temp = this.heap[indexOne];

        this.heap[indexOne] = this.heap[indexTwo];

        this.heap[indexTwo] = temp;

    }

 

    peek() {

        if (this.heap.length === 0) {

            return null;

        }

        return this.heap[0];

    }

     

    // Removing an element will reomve the

    // top element with highest priority then

    // heapifyDown will be called 

    remove() {

        if (this.heap.length === 0) {

            return null;

        }

        const item = this.heap[0];

        this.heap[0] = this.heap[this.heap.length - 1];

        this.heap.pop();

        this.heapifyDown();

        return item;

    }

 

    add(item) {

        this.heap.push(item);

        this.heapifyUp();

    }

 

    heapifyUp() {

        let index = this.heap.length - 1;

        while (this.hasParent(index) && this.parent(index) > this.heap[index]) {

            this.swap(this.getParentIndex(index), index);

            index = this.getParentIndex(index);

        }

    }

 

    heapifyDown() {

        let index = 0;

        while (this.hasLeftChild(index)) {

            let smallerChildIndex = this.getLeftChildIndex(index);

            if (this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index)) {

                smallerChildIndex = this.getRightChildIndex(index);

            }

            if (this.heap[index] < this.heap[smallerChildIndex]) {

                break;

            } else {

                this.swap(index, smallerChildIndex);

            }

            index = smallerChildIndex;

        }

    }

     

    printHeap() {

        var heap =` ${this.heap[0]} `

        for(var i = 1; i<this.heap.length;i++) {

            heap += ` ${this.heap[i]} `;

        }

        console.log(heap);

    }

}

 

// Creating the Heap

var heap = new MinHeap();

 

// Adding The Elements

heap.add(10);

heap.add(15);

heap.add(30);

heap.add(40);

heap.add(50);

heap.add(100);

heap.add(40);

 

// Printing the Heap

heap.printHeap();

 

// Peeking And Removing Top Element

console.log(heap.peek());

console.log(heap.remove());

 

// Printing the Heap

// After Deletion.

heap.printHeap();

Выход

 10  15  30  40  50  100  40 
10
10
 15  40  30  40  50  100