Implementation of a min-heap and heapsort

heap.js

var MinHeap = {
  _rootLevel: 1,
  init: function() {
    this.arr = []
    this.level = this._rootLevel
  },
  insert: function(value) {
    this.arr[this.level] = value
    this._bubbleUp(this.level)
  },
  _bubbleUp: function(level) {
    let parent = this._getParentLevel(level)
    if (this.arr[level] >= this.arr[parent] || level == 1) {
      this.level++;
      return;
    }
    this._swap(level, parent)
    this._bubbleUp(parent)
  },
  extractMin: function() {
    let rootLevel = this._getRootLevel()
    let lastLevel = this._getLastLevel()
    let min = this.arr[rootLevel]
    let valueToBubbleDown = this.arr[lastLevel]

    this.arr[rootLevel] = valueToBubbleDown
    this.level--
    this._bubbleDown(rootLevel)
    return min
  },
  _bubbleDown: function(level) {
    let left = this._getLeftChild(level)
    let right = this._getRightChild(level)
    let smallest
    if (left >= this.level) {
      this.arr.pop()
      return
    }
    if (left <= this.level && this.arr[left] < this.arr[level]) {
      smallest = left
    } else {
      smallest = level
    }
    if (right <= this.level && this.arr[right] < this.arr[smallest]) {
      smallest = right
    }
    this._swap(level, smallest)
    this._bubbleDown(smallest)
  },
  _getParentLevel: function(level) {
    var calculation = level / 2
    if (level % 2 == 0) {
      return calculation
    } else {
      return Math.floor(calculation)
    }
  },
  _swap: function(currentLevel, levelToSwap){
    let currValue = this.arr[currentLevel]
    let valueToSwap = this.arr[levelToSwap]
    this.arr[currentLevel] = valueToSwap
    this.arr[levelToSwap] = currValue
  },
  _getLastLevel: function() {
    return this.level - 1
  },
  _getRootLevel: function(){
    return this._rootLevel
  },
  _getLeftChild: function(level) {
    return level * 2
  },
  _getRightChild: function(level) {
    return (level * 2) + 1
  },
  heapSort: function() {
    let minSortedArr = []
    for (var i = this.arr.length; i >= 2; i--) {
      let val = this.extractMin()
      minSortedArr.push(val)
    }
    return minSortedArr
  },
  buildMinHeap: function(arr) {
    arr.forEach(index => {
      this.insert(index)
    })
  },
  peek: function() {
    return this.arr[this._getRootLevel()]
  }
}

var ArrayMerger = Object.create(MinHeap)
ArrayMerger.merge = function(kManyLists) {
  kManyLists.forEach(list => {
    this.buildMinHeap(list)
  })
  return this.heapSort()
},

var list = [[1,2,3],[4,5,6],[4,5,7,8,9,10],[1,2,41,55]]
var mergeArraysImplementation = Object.create(ArrayMerger)
mergeArraysImplementation.init()
mergeArraysImplementation.merge(list)
console.log(mergeArraysImplementation.heapSort())

Summary
This gist demonstrates an implementation of a min-heap, and a starting point for the sol'n to the "merge k sorted lists" problem.
What this gist does not cover - A heap sort implementation that accounts for duplicate values. However, below outlines two solutions to cover this case.

If we were to implement the full k-sorted lists algorithm, there are a few solutions we could choose from:

• We could either implement a hashmap, use an object, or a Map data structure to serve as a "de-dupe" table in combination with our heap.

  • Analysis: The heap takes O(n) space, implementing a hashmap would cost O(n). The total cost to implement both data structures would be O(n) + O(n) = O(2n). Remember we drop constants in time/space complexity analysis.
  • Note: store a reference to an object in this data structure. For example, suppose an object in our system is 100bytes and a reference to the object (ID:string) is < 8 bytes (in javascript.) With 1000 objects, we'd be storing 100kb. With 1000 reference IDs, we'd be storing 2kb bytes. Big difference.

• We call peek() before each extractMin() call to check whether or not the number returned is a duplicate of the most recent element removed from the heap. i.e. We keep a reference to the previous element returned from extractMin().