Implementation of a (max) heap data structure in JavaScript

javascript-max-heap.js

class MaxHeap {
  // creates an array of given length
  constructor(length) {
    this.data = new Array(length)
    this.size = 0
  }

  // helpers

  rehash = () => {
    // create a new array that is twice the size of current array
    let newData = new Array(this.data.length * 2)

    // copy all values in current array to new array
    // not going through whole array as only .75 array should have values at the point of rehashing
    let i = 0

    while (this.data[i] !== undefined) {
      newData[i] = this.data[i]
      i++
    }

    // assign new array to current array
    this.data = newData
  }

  // moves a bigger value up to right place
  bubbleUp = valueIndex => {
    // get new value from index
    let value = this.data[valueIndex]

    let parentIndex = Math.floor((valueIndex - 1) / 2)
    let parentValue = this.data[parentIndex]

    // if new value is larger than parent value 
    // (as this is a max heap, larger values should be moved up)
    if (value > parentValue) {
      // swap spots of parent and new value 
      let temp = parentValue

      this.data[parentIndex] = value
      this.data[valueIndex] = temp

      // perform same operation from the current spot 
      this.bubbleUp(parentIndex)
      // if at right place, return
    } else return
  }

  // moves a smaller value down to right place
  bubbleDown = valueIndex => {
    // get new value from index
    let value = this.data[valueIndex]
    
    let leftChildIndex = 2 * valueIndex + 1 // 7
    let leftChildValue = this.data[leftChildIndex] // x
    
    let rightChildIndex = 2 * valueIndex + 2 // 8
    let rightChildValue = this.data[rightChildIndex] // x
    
    // if not any of children are undefined
    if (leftChildValue && rightChildValue) {
      // if either of children are larger
      if (value < leftChildValue || value < rightChildValue) {
        // get larger of two children
        let largerChildValue = Math.max(leftChildValue, rightChildValue)
        let largerChildIndex = largerChildValue === leftChildValue ? leftChildIndex : rightChildIndex

        // swap spots with smaller child
        let temp = largerChildValue

        this.data[largerChildIndex] = value
        this.data[valueIndex] = temp

        // continue same from current spot
        this.bubbleDown(largerChildIndex)
      } else return
    // if right child is undefined and left child is larger, we need to swap one last time
    } else if (rightChildValue === undefined && value < leftChildValue) {
      let temp = leftChildValue

      this.data[leftChildIndex] = value
      this.data[valueIndex] = temp

      // perform same operation from the current spot 
      this.bubbleDown(valueIndex)
    // if both are undefined, return.
    // they are vacant spots
    } else return
  }

  // helper functions end

  insert = value => {
    // if array empty, just insert at root,
    // increase size
    // and return
    if (this.size === 0) {
      this.data[0] = value
      this.size++
      return
    }

    // load factor = filled slots / total slots
    let loadFactor = this.size / this.data.length

    // if gte to .75, increase (double) the size
    if (loadFactor >= .75) this.rehash()

    // insert new value at the end
    this.data[this.size] = value

    // move new value up the tree to the right place from current spot
    this.bubbleUp(this.size)

    this.size++
  }

  removeRoot = () => {
    // get the lowest, right-most value and
    // assign to root
    this.data[0] = this.data[this.size - 1]
    this.data[this.size - 1] = undefined

    // move new root value down the tree to the right place 
    // swapping with the smaller of two children
    this.bubbleDown(0)

    this.size--
  }

  getMax = () => {
    return this.data[0]
  }
}

// tests

let heap = new MaxHeap(10)

// heap.insert(1)
// heap.insert(9)
// heap.insert(13)
// heap.insert(8)
// heap.insert(20)
// heap.insert(2)
// heap.insert(2)
// heap.insert(2)
// console.log(heap.size)
// console.log(heap.data)

// heap.removeRoot()
// console.log('size', heap.size)
// console.log(heap.data)
// heap.removeRoot()
// console.log('size', heap.size)
// console.log(heap.data)
// heap.removeRoot()
// console.log('size', heap.size)
// console.log(heap.data)

// heap.insert(26)
// heap.insert(76)
// heap.insert(90)
// heap.insert(-90)
// console.log(heap.data)

// console.log(heap.getMax())