MaxHeap with heapify & Heap sort

heapify.js

class MaxHeap {
  constructor(arr = []){
    this.size = 0
    this.values = this._heapify(arr)
  }
  
  insert(value){
    // If no value, do nothing
    if (value === undefined) return
    // Insert the value, and increment the size of the heap
    this.values.push(value)
    this.size++
    // Check to see if there is not more than 1 item in the heap
    // If there is only 1 item, there is no need to bubble up
    if (this.size > 1) this._bubbleUp()
    return this.values
  }
  
  extract(){
    if (this.size === 0) return
    const lastIndex = this.size - 1
    this.size--
    this._swap(0, lastIndex)
    const extractValue = this.values.pop()
    if (this.size > 1) this._trickleDown()
    return extractValue
  }
  
  // Helper function using object destructuring to swap the elements at two indices
  _swap(index1, index2){
    [this.values[index1], this.values[index2]] = [this.values[index2], this.values[index1]]
  }
  
  _heapify(arr){
    if (this.size > 0) return // Optional: Prevent overriding existing heap values
    this.size = arr.length
    /** 
    * To prevent mutating current array, replace line 18 with 
    * this.values = [...arr]
    */
    this.values = arr 
    const nodeCount = this.size - 1
    // Finds the last node of the tree that has children
    let cIdx = Math.floor((nodeCount - 2)/2)
    /** For each node up through the root, 
    * call trickleDown
    */
    for (let i = cIdx; i >= 0; i--){
      this._trickleDown(i)
    }
    return this.values
  }
  
  _bubbleUp(){
    // Grab the most recently added value and its parent
    let currentIndex = this.size - 1
    let parentIndex = Math.floor( (currentIndex - 1) / 2 )
    
    // Swap the new node with its parent until the new node either
    // becomes the root, or is no longer greater than its parent
    while (parentIndex >= 0 && this.values[currentIndex] > this.values[parentIndex]){
      this._swap(currentIndex, parentIndex)
      currentIndex = parentIndex
      parentIndex = Math.floor((currentIndex - 1) / 2 )
    }
  }
  
  _trickleDown(start = 0, stop = this.size){
    let currentIndex = start
    /** 
    * These will be the indexes corresponding to the left and right 
    * child of the node at currentIndex
    * swapIdx will be which of the children the currentIndex will
    * actually switch with, if any
    */
    let leftIdx, rightIdx, swapIdx
    while (true) {
        leftIdx = 2 * currentIndex + 1
        rightIdx = 2 * currentIndex + 2
        swapIdx = null
        /**
        * If there is a valid left child and it is greater than the current value,
        * prepare to swap it
        */
        if (
          leftIdx < stop &&
          this.values[currentIndex] < this.values[leftIdx]
        ) {
          swapIdx = leftIdx
        }
        /**
        * If there is a valid right child and it is greater than the current value,
        * prepare to swap it if we haven't already prepared to swap with left child.
        * If we have prepared to swap with left child, we should only choose to swapIdx
        * with the right child instead if it is greater than the left child, meaning
        * it better fits the heap rule
        */
        if (
          rightIdx < stop &&
          ((swapIdx === null &&
            this.values[currentIndex] < this.values[rightIdx]) ||
            (swapIdx !== null && this.values[rightIdx] > this.values[leftIdx]))
        ) {
          swapIdx = rightIdx
        }
        if (swapIdx === null) break // If no possibel swap was ID'd, we're done
        // Swap the parent with the identified child, update the currentIndex, and repeat
        this._swap(currentIndex, swapIdx)
        currentIndex = swapIdx
    }
  }

  static heapSort(arr){
    const heap = new MaxHeap(arr)
    for (let i = arr.length - 1; i > 0; i--){
      heap._swap(0,i)
      heap._trickleDown(0, i)
    }
    return heap.values
  }
}