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

Минимальная 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

Читайте также:  JSON-парсер JavaScript
Оцените статью
bestprogrammer.ru
Добавить комментарий