如何正确转换使用PriorityQueue的Java方法为JavaScript代码

现有一段Java代码需要编写等效的JavaScript实现，核心难点是Java原生内置的PriorityQueue（优先级队列）在JavaScript中没有原生支持，自行编写的JS版本无法得到正确结果，该测试用例的预期返回结果为6。

原Java代码 #

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){
        // 核心优先级队列逻辑
        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;
    }
}

原有错误JS实现 #

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))

错误点说明 #

• 排序比较逻辑不符合JS数组sort方法的规范：sort的比较函数需要统一返回负数/0/正数来表示优先级，原有写法在a[0] <= b[0]时直接返回索引差，没有正确处理a[0] < b[0]和a[0] == b[0]两种场景的排序规则，导致排序结果混乱。
• 入队参数错误：原Java逻辑中新入队元素的第二个值是柜台索引index，原有写法错误传入了柜台服务时长counter[index]，破坏了队列元素的结构。
• 用普通数组+全局排序的方式模拟优先级队列效率极低，且每次push新元素后没有重新排序，无法保证每次取出的是优先级最高的元素。

正确JavaScript实现 #

基于最小堆实现和Java逻辑完全一致的优先级队列，代码如下：

// 最小堆实现的优先级队列，和Java PriorityQueue逻辑对齐
class PriorityQueue {
  constructor(comparator) {
    this.heap = [];
    this.comparator = comparator;
  }

  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  getParentIndex(i) {
    return Math.floor((i - 1) / 2);
  }

  getLeftChildIndex(i) {
    return 2 * i + 1;
  }

  getRightChildIndex(i) {
    return 2 * i + 2;
  }

  // 入队后上浮调整
  add(val) {
    this.heap.push(val);
    this.siftUp(this.heap.length - 1);
  }

  siftUp(i) {
    while (i > 0) {
      const parentIdx = this.getParentIndex(i);
      if (this.comparator(this.heap[parentIdx], this.heap[i]) <= 0) break;
      this.swap(i, parentIdx);
      i = parentIdx;
    }
  }

  // 出队后下沉调整
  poll() {
    if (this.heap.length === 0) return null;
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.siftDown(0);
    }
    return top;
  }

  siftDown(i) {
    const heapLength = this.heap.length;
    while (true) {
      let priorityIdx = i;
      const leftIdx = this.getLeftChildIndex(i);
      const rightIdx = this.getRightChildIndex(i);
      if (leftIdx < heapLength && this.comparator(this.heap[leftIdx], this.heap[priorityIdx]) < 0) {
        priorityIdx = leftIdx;
      }
      if (rightIdx < heapLength && this.comparator(this.heap[rightIdx], this.heap[priorityIdx]) < 0) {
        priorityIdx = rightIdx;
      }
      if (priorityIdx === i) break;
      this.swap(i, priorityIdx);
      i = priorityIdx;
    }
  }
}

const findTotalTime = (counter, k) => {
  // 比较逻辑和Java完全对齐：先比较累计耗时，耗时相同则比较柜台索引，值小的优先级高
  const pq = new PriorityQueue((a, b) => a[0] === b[0] ? a[1] - b[1] : a[0] - b[0]);

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

  let endTime = 0;
  for (let i = 0; i <= k; i++) {
    const [counterTime, index] = pq.poll();
    endTime = counterTime + counter[index];
    pq.add([endTime, index]);
  }
  return endTime;
}

// 测试用例，输出结果为6，符合预期
console.log(findTotalTime([3,2,5], 4));

内容的提问来源于stack exchange，提问作者Caleb Oki