Min Heap

JavaScript

'use strict';

function MinHeap(arr) {
    this.heapSize = arr.length;
    this.items = arr;
    this.heapify();
}

MinHeap.parent = function (index) {
    return Math.floor((index - 1) / 2);
};

MinHeap.left = function (index) {
    return 2 * index + 1;
};

MinHeap.right = function (index) {
    return 2 * index + 2;
};

MinHeap.prototype.heapify = function () {
    for (var i = this.heapSize - 1; i >= 0; i--) {
        this.bubbleUp(i);
    }
};

MinHeap.prototype.bubbleUp = function (index) {
    if (index < 0) {
        return;
    }
    
    if (index >= this.heapSize) {
        console.log('Invalid index sent to bubbleUp: %s', index);
        return;
    }

    var leftIndex = MinHeap.left(index);
    var rightIndex = MinHeap.right(index);

    var minimum = index;

    if (leftIndex < this.heapSize && this.items[minimum] > this.items[leftIndex]) {
        minimum = leftIndex;
    }

    if (rightIndex < this.heapSize && this.items[minimum] > this.items[rightIndex]) {
        minimum = rightIndex;
    }

    if (index !== minimum) {
        this.swap(index, minimum);
        this.bubbleUp(minimum);
    }
};

MinHeap.prototype.swap = function (a, b) {
    var temp = this.items[a];
    this.items[a] = this.items[b];
    this.items[b] = temp;
};

MinHeap.prototype.insert = function (key) {
    this.items[this.heapSize] = key;
    this.heapSize += 1;
    this.bubbleUp(MinHeap.parent(this.heapSize - 1));
};

MinHeap.prototype.findMin = function () {
    return this.items[0];
};

MinHeap.prototype.extractMin = function () {
    var min = this.items[0];
    this.items[0] = this.items[this.heapSize - 1];
    this.items.splice(this.heapSize - 1);
    this.heapSize -= 1;
    this.heapify(0);
    return min;
};


// TEST

var array = [10,5,3,8,11,3,1,2,5,2];
var heap = new...