educative.io

Educative

Connecting ropes Javascript solution

const Heap = require('./collections/heap'); //http://www.collectionsjs.com


function minimum_cost_to_connect_ropes(ropeLengths) {
  // add all ropes to the min heap
  const minHeap = new Heap(ropeLengths, null, ((a, b) => b - a));

  // go through the values of the heap, in each step take top (i.e., lowest) rope lengths from the min heap
  // connect them and push the result back to the min heap.
  // keep doing this until the heap is left with only one rope
  let result = 0;
  while (minHeap.length > 1) {
    const temp = minHeap.pop() + minHeap.pop();
    result += temp;
    minHeap.push(temp);
  }

  return result;
}

Shouldn't the naming of the heap be `maxHeap`, since we are storing all the elements in a descending order and the `root` is always the largest number in the array?

----
Type your question above this line.

Course: https://www.educative.io/collection/5668639101419520/5671464854355968
Lesson: https://www.educative.io/collection/page/5668639101419520/5671464854355968/5668515822436352

I think you misunderstood something, the aim is to take the lowest rope length at each step and that is being achieved by creating a min heap where the root is always the minimum value.