Translate this Java method to JavaScript

Question

I have this Java code below, that I am trying to write its JavaScript equivalent. The code uses a priority queue which is native to Java but not JavaScript. I have attempted to write a similar code in JavaScript but I am not getting the required result. How do I write this, particularly the priority queue section in the Java code. Please note that the required result of this method call is 6

Java Code:

public class Main {
    public static void main(String[] args) {
        int [] counter = new int[]{3,2,5};
        int k=4;
        System.out.println(findTotalTime(counter,k));
    }
    
    public static int findTotalTime(int[] counter, int k){

        //Priority queue section I am mostly curious about

        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->
                (a[0] == b[0] ? 
                 Integer.compare(a[1],b[1]) : 
                 Integer.compare(a[0],b[0])));

        for(int i=0;i<counter.length;i++)
            pq.add(new int[]{0,i});

        int endTime=0;

        for(int i=0;i<=k;i++){
            int info[] = pq.poll();
            int counterTime = info[0];
            int index = info[1];
            
            endTime = counterTime + counter[index];

            pq.add(new int[]{endTime, index});
        }
        return endTime;
    }
}

My attempt at a JavaScript equivalent:

const findTotalTime = (counter, k) => {
  let queue = []

  for (let i = 0; i < counter.length; i++) {
    queue.push([0, i])
  }

  queue.sort((a, b) => {return a[0] <= b[0] ? a[1] - b[1] : a[0] - b[0]})

  let endTime = 0

  for (let i = 0; i <= k; i++) {
    let info = queue.shift()
    let [counterTime, index] = info

    endTime = counterTime + counter[index]

    queue.push([endTime, counter[index]])
  }
  return endTime
}

console.log(findTotalTime([3, 2, 5], 4))

PriorityQueue always keeps the ordering by the comparator, even when adding new elements, whereas in Javascript, you only sort the list after the initialization, and thus the queue is not ordered correctly when polling in the second for loop. — jh316, Jul 08 '22 at 22:16
Does this answer your question? [Efficient way to implement Priority Queue in Javascript?](https://stackoverflow.com/questions/42919469/efficient-way-to-implement-priority-queue-in-javascript) — tgdavies, Jul 08 '22 at 23:12
@tgdavies I used the heap there but did not get the desired result. Please see code here: https://gist.github.com/caleboki/51d3f865da28b0ff74c0d0715bcfac6a — Caleb Oki, Jul 09 '22 at 01:23

trincot · Accepted Answer · 2022-07-10T14:29:45.503

Apart from the lacking priority queue, there are also these issues:

The argument to queue.push is wrong. It should be [endTime, index] instead of [endTime, counter[index]]
The comparator passed to sort is not correct. It should be (a, b) => a[0] - b[0] || a[1] - b[1]
As there is no heap implementation, the loop needs extra logic to ensure that the least entry is popped from the queue in each iteration of the loop. One naive (not efficient) way is to move the sort call inside the loop.

With those changes your code works:

const findTotalTime = (counter, k) => {
  let queue = []

  for (let i = 0; i < counter.length; i++) {
    queue.push([0, i])
  }

  let endTime = 0;

  for (let i = 0; i <= k; i++) {
    queue.sort((a, b) => a[0] - b[0] || a[1] - b[1]); // comparator fix & keep sorted
    let info = queue.shift();
    let [counterTime, index] = info;
    endTime = counterTime + counter[index];
    queue.push([endTime, index]);  // <-- fix
  }
  return endTime;
}

console.log(findTotalTime([3, 2, 5], 4));

To make it work with a priority queue, you'll need to add an implementation. I would suggest the one I provided in this answer. However, I'd like to first suggest a simplification so that you don't actually need to work with pairs, but can work with integers (as holding both the value and index):

As the index is always in the range 0..n-1, you can multiply the value with n, and add the index to it. This way you only have one integer which immediately represents its priority. This allows for a simpler implementation of a heap. This leads to the following code:

// MinHeap implementation with only push/pop. No payload, only keys.
const MinHeap = {
    pop(arr) {
        let key = arr.pop();
        if (!arr.length) return key;
        let oldKey = arr[0];
        let i = 0;
        while (true) {
            let j = i*2+1;
            if (j+1 < arr.length && arr[j] > arr[j+1]) j++;
            if (j >= arr.length || key <= arr[j]) break;
            arr[i] = arr[j];
            i = j;
        }
        arr[i] = key;
        return oldKey;
    },
    push(arr, key) {
        let i = arr.length,
            j;
        while ((j = (i-1)>>1) >= 0 && key < arr[j]) {
            arr[i] = arr[j];
            i = j;
        }
        arr[i] = key;
        return arr;
    }
};

const findTotalTime = (counter, k) => {
    let n = counter.length;
    let queue = [...Array(n).keys()];
    let endTime = 0;
    for (let i = 0; i <= k; i++) {
        let key = MinHeap.pop(queue);
        let index = key % n;
        let counterTime = (key - index) / n;
        endTime = counterTime + counter[index];
        MinHeap.push(queue, endTime * n + index);
    }
    return endTime;
}

console.log(findTotalTime([3, 2, 5], 4));

Translate this Java method to JavaScript

1 Answers1