Java 优先级队列实现

PriorityQueue.js

class PriorityQueue {
  #top = 0;
  #heap;
  #comparator;
  
  constructor(comparator = (a, b) => a > b) {
    this.#heap = [];
    this.#comparator = comparator;
  }
  #parent(i) {
    return ((i+1) >>> 1) - 1;
  }
  #left(i) {
    return (i<<1) + 1;
  }
  #right(i) {
    return (i+1) << 1;
  }
  #greater(i, j) {
    return this.#comparator(this.#heap[i], this.#heap[j]);
  }
  #swap(i, j) {
    [this.#heap[i], this.#heap[j]] = [this.#heap[j], this.#heap[i]];
  }
  #siftUp() {
    let node = this.size() - 1;
    while (node > this.#top && this.#greater(node, this.#parent(node))) {
      this.#swap(node, this.#parent(node));
      node = this.#parent(node);
    }
  }
  #siftDown() {
    let node = this.#top;
    while (
      (this.#left(node) < this.size() && this.#greater(this.#left(node), node)) ||
      (this.#right(node) < this.size() && this.#greater(this.#right(node), node))
    ) {
      let maxChild = (this.#right(node) < this.size() && this.#greater(this.#right(node), this.#left(node))) ? this.#right(node) : this.#left(node);
      this.#swap(node, maxChild);
      node = maxChild;
    }
  }
  size() {
    return this.#heap.length;
  }
  isEmpty() {
    return this.size() == 0;
  }
  peek() {
    return this.#heap[this.#top];
  }
  push(...values) {
    values.forEach(value => {
      this.#heap.push(value);
      this.#siftUp();
    });
    return this.size();
  }
  pop() {
    const poppedValue = this.peek();
    const bottom = this.size() - 1;
    if (bottom > this.#top) {
      this.#swap(this.#top, bottom);
    }
    this.#heap.pop();
    this.#siftDown();
    return poppedValue;
  }
  replace(value) {
    const replacedValue = this.peek();
    this.#heap[this.#top] = value;
    this.#siftDown();
    return replacedValue;
  }
}