优先队列

实现

class PriorityQueue {
  constructor() {
    this.length = 0;
    this.data = [];
  }
  compareTo(a, b) {
    return a - b;
  }
  shiftUp(index) {
    while (index > 0) {
      let parent = Math.floor((index - 1) / 2);
      if (this.compareTo(this.data[index], this.data[parent]) < 0) {
        [this.data[index], this.data[parent]] = [
          this.data[parent],
          this.data[index],
        ];
        index = parent;
      } else {
        return;
      }
    }
  }
  shiftDown(index) {
    while (index * 2 + 1 <= this.length - 1) {
      let child = index * 2 + 1;
      if (
        child + 1 <= this.length - 1 &&
        this.compareTo(this.data[child], this.data[child + 1]) > 0
      ) {
        child++;
      }
      if (this.compareTo(this.data[index], this.data[child]) > 0) {
        [this.data[index], this.data[child]] = [
          this.data[child],
          this.data[index],
        ];
        index = child;
      } else {
        return;
      }
    }
  }
  add(value) {
    this.data.push(value);
    this.length++;
    if (this.length != 1) {
      this.shiftUp(this.length - 1);
    }
  }
  poll() {
    const result = this.data[0];
    if (this.length == 1) {
      this.data.pop();
    } else {
      this.data[0] = this.data.pop();
    }
    this.length--;
    this.shiftDown(0);
    return result;
  }
  peek() {
    return this.data[0];
  }
  isEmpty() {
    return this.data.length === 0;
  }
}