class MinHeap<T = number> {
  heap: T[] = [];

  // 时间复杂度: O(1)
  peek(): T | null {
    return this.heap.length ? this.heap[0] : null;
  }

  // 时间复杂度: O(log n)
  add(value: T) {
    this.heap.push(value);
    this.heapifyUp();
  }

  // 时间复杂度: O(log n)
  poll(): T | null {
    if (!this.heap.length) return null;
    const result = this.heap[0];
    const end = this.heap.pop()!;
    if (this.heap.length) {
      this.heap[0] = end;
      this.heapifyDown();
    }
    return result;
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index] >= this.heap[parentIndex]) break;
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    }
  }

  heapifyDown() {
    let index = 0;
    const length = this.heap.length;
    while (true) {
      let left = 2 * index + 1;
      let right = 2 * index + 2;
      let smallest = index;

      if (left < length && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < length && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest === index) break;

      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }
}

class PriorityQueue<T = number> {
  private heap = new MinHeap<{ priority: number; value: T }>();

  // 时间复杂度: O(log n)
  enqueue(value: T, priority: number) {
    this.heap.add({ value, priority });
  }

  // 时间复杂度: O(log n)
  dequeue(): T | null {
    const item = this.heap.poll();
    return item ? item.value : null;
  }
}