/**
 * @description 表示最小堆中的一个节点。
 *
 * `name` 用于在 `indexMap` 中快速定位节点，
 * `endAt` 用作最小堆的排序键，值越小表示越早到期，优先级越高。
 */
interface HeapNode<Name extends string> {
  name: Name
  endAt: number
}

/**
 * @description 提供一个按 `endAt` 升序排列的最小堆。
 *
 * 该实现同时维护：
 * 1. `heap`：保存二叉堆结构本身，用于快速获取最小值。
 * 2. `indexMap`：记录名称到数组索引的映射，用于按名称 $O(1)$ 定位节点，
 * 从而支持高效的更新和删除。
 *
 * 这个堆特别适合“按时间先后触发”的场景，例如过期调度器。
 */
export class MinHeap<Name extends string> {
  /**
   * @description 使用数组存储完全二叉树结构。
   * 父子节点关系遵循：
   * - parent = Math.floor((index - 1) / 2)
   * - left = index * 2 + 1
   * - right = index * 2 + 2
   */
  private heap: Array<HeapNode<Name>> = []

  /**
   * @description 记录节点名称在 `heap` 数组中的当前位置。
   *
   * 这样删除指定名称的节点时，不需要线性扫描整个堆。
   */
  private indexMap = new Map<Name, number>()

  /**
   * @description 返回当前堆中的节点数量。
   */
  size(): number {
    return this.heap.length
  }

  /**
   * @description 查看堆顶节点但不移除。
   *
   * 堆顶始终是当前 `endAt` 最小的节点，也就是最早应被处理的节点。
   */
  peek(): HeapNode<Name> | undefined {
    return this.heap[0]
  }

  /**
   * @description 向堆中插入一个新节点。
   *
   * 新节点会先追加到数组末尾，再通过上浮恢复最小堆性质。
   */
  push(node: HeapNode<Name>): void {
    const index = this.heap.length
    this.heap.push(node)
    this.indexMap.set(node.name, index)
    this.bubbleUp(index)
  }

  /**
   * @description 按名称移除一个节点。
   *
   * 过程如下：
   * 1. 借助 `indexMap` 找到目标节点位置。
   * 2. 用最后一个节点填补被删除的位置。
   * 3. 根据替换节点与父/子节点的大小关系，分别尝试下沉和上浮，恢复堆结构。
   */
  remove(name: Name): void {
    const index = this.indexMap.get(name)
    if (index === undefined) {
      return
    }

    const last = this.heap.pop()!
    this.indexMap.delete(name)

    // 被删除节点本来就在数组末尾时，弹出后无需再做任何调整。
    if (index === this.heap.length) {
      return
    }

    this.heap[index] = last
    this.indexMap.set(last.name, index)

    // 替换进来的节点可能比子节点大，也可能比父节点小，
    // 因此两个方向都尝试一次，以覆盖所有位置变化情况。
    this.bubbleDown(index)
    this.bubbleUp(index)
  }

  /**
   * @description 移除并返回堆顶节点。
   *
   * 当堆为空时返回 `undefined`。
   */
  pop(): HeapNode<Name> | undefined {
    if (this.heap.length === 0) {
      return undefined
    }

    const top = this.heap[0]
    if (top === undefined) {
      return undefined
    }

    this.remove(top.name)
    return top
  }

  /**
   * @description 交换两个索引位置上的节点，并同步更新它们在 `indexMap` 中的记录。
   */
  private swap(i: number, j: number): void {
    const a = this.heap[i]
    const b = this.heap[j]

    if (a === undefined || b === undefined) {
      return
    }

    this.heap[i] = b
    this.heap[j] = a

    this.indexMap.set(a.name, j)
    this.indexMap.set(b.name, i)
  }

  /**
   * @description 让指定索引处的节点持续向上移动，直到满足最小堆性质。
   *
   * 适用于插入新节点，或某个节点的排序键变小之后的重排。
   */
  private bubbleUp(index: number): void {
    let currentIndex = index

    while (currentIndex > 0) {
      const parent = Math.floor((currentIndex - 1) / 2)
      const parentNode = this.heap[parent]
      const currentNode = this.heap[currentIndex]

      if (parentNode === undefined || currentNode === undefined) {
        break
      }

      if (parentNode.endAt <= currentNode.endAt) {
        break
      }

      this.swap(parent, currentIndex)
      currentIndex = parent
    }
  }

  /**
   * @description 让指定索引处的节点持续向下移动，直到满足最小堆性质。
   *
   * 每次从当前节点与左右子节点中选出 `endAt` 最小者，
   * 若最小者不是当前节点，则交换并继续向下检查。
   */
  private bubbleDown(index: number): void {
    const length = this.heap.length
    let currentIndex = index

    while (true) {
      let smallest = currentIndex
      const left = currentIndex * 2 + 1
      const right = currentIndex * 2 + 2
      const smallestNode = this.heap[smallest]
      const leftNode = this.heap[left]
      const rightNode = this.heap[right]

      if (smallestNode === undefined) {
        break
      }

      // 先用左子节点与当前最小值比较。
      if (left < length && leftNode !== undefined && leftNode.endAt < smallestNode.endAt) {
        smallest = left
      }

      const nextSmallestNode = this.heap[smallest]

      // 再基于最新的最小候选与右子节点比较。
      if (
        right < length &&
        rightNode !== undefined &&
        nextSmallestNode !== undefined &&
        rightNode.endAt < nextSmallestNode.endAt
      ) {
        smallest = right
      }

      if (smallest === currentIndex) {
        break
      }

      this.swap(currentIndex, smallest)
      currentIndex = smallest
    }
  }
}