minCostConnect.js

function MinHeap() {
  this.arr = new Array()
}

MinHeap.prototype.push = function push(data, weight) {
  this.arr.push({ data, weight })
  if(this.arr.length <= 1) return
  let current = this.arr.length - 1
  let parent = Math.floor(current/2)
  while(parent >= 0 && current > 0 && this.arr[parent].weight > this.arr[current].weight) {
    swap(this.arr, parent, current)
    current = parent
    parent = Math.floor(parent/2)
  }
}

MinHeap.prototype.pop = function pop() {
  if(this.arr.length === 0) return
  const element = this.arr[0]
  this.arr[0] = this.arr[this.arr.length - 1]
  this.arr.length -= 1
  this.heapify(0)
  return element
}

MinHeap.prototype.heapify = function heapify(index) {
  let left = (index * 2) + 1, right = left + 1
  let smallest = index
  if(left && this.arr[left] && this.arr[left].weight < this.arr[smallest].weight) {
    smallest = left
  }
  if(right && this.arr[right] && this.arr[right].weight < this.arr[smallest].weight) {
    smallest = right
  }
  if(smallest !== index) {
    swap(this.arr, smallest, index)
    this.heapify(smallest)
  }
}

MinHeap.prototype.peek = function peek() {
  if(this.arr.length === 0) return null
  return this.arr[0]
}
MinHeap.prototype.size = function size() {
  return this.arr.length
}

function swap(arr, left, right) {
  const temp = arr[left]
  arr[left] = arr[right]
  arr[right] = temp
}

class DisjointSet {
  constructor(length) {
    this.arr = new Array(length).fill(Infinity)
    this.arr = this.arr.map((_, index) => index)
  }
  find = (key) => {
    if(this.arr[key] === key) return key
    return this.find(this.arr[key])
  }
  union = (keyA, keyB) => {
    const parentA = this.find(keyA)
    const parentB = this.find(keyB)
    if(parentA !== parentB) {
      for(let i=0; i<this.arr.length; i++) {
        if(this.arr[i] === parentB) this.arr[i] = parentA
      }
    }
  }
  isConnected = (keyA, keyB) => {
    return this.find(keyA) === this.find(keyB)
  }
}

function findDistance(pointA, pointB) {
  const xDistance = Math.abs(pointA[0] - pointB[0])
  const yDistance = Math.abs(pointA[1] - pointB[1])
  return xDistance + yDistance
}

function minCostConnectPoints(points) {
  const minHeap = new MinHeap()
  for(let i=0; i<points.length; i++) {
    for(let j=i+1; j<points.length; j++) {
      const distance = findDistance(points[i], points[j])
      minHeap.push({from: i, to: j}, distance)
    }
  }
  const disjointSet = new DisjointSet(points.length)
  let edgesCount = 0, minCost = 0
  while(edgesCount < points.length - 1 && minHeap.size() > 0) {
    let current = minHeap.pop()
    if(disjointSet.isConnected(current.data.from, current.data.to) === false) {
      minCost += current.weight
      disjointSet.union(current.data.from, current.data.to)
      edgesCount++
    }
  }
  return minCost
}