1
package minheap
2

3
// MinHeap 是泛型最小堆，要求元素满足 constraints.Ordered
4
type MinHeap[T interface{ Less(T) bool }] struct {
5
    data []T
6
}
7

8
func New[T interface{ Less(T) bool }]() *MinHeap[T] {
9
    return &MinHeap[T]{data: make([]T, 0)}
10
}
11

12
// Push 插入元素
13
func (h *MinHeap[T]) Push(val T) {
14
    h.data = append(h.data, val)
15
    h.siftUp(len(h.data) - 1)
16
}
17

18
// Pop 弹出最小元素
19
func (h *MinHeap[T]) Pop() (T, bool) {
20
    if len(h.data) == 0 {
21
        var zero T
22
        return zero, false
23
    }
24
    root := h.data[0]
25
    last := h.data[len(h.data)-1]
26
    h.data = h.data[:len(h.data)-1]
27
    if len(h.data) > 0 {
28
        h.data[0] = last
29
        h.siftDown(0)
30
    }
31
    return root, true
32
}
33

34
// 上浮：与父节点比较，比父小则交换
35
func (h *MinHeap[T]) siftUp(i int) {
36
    for i > 0 {
37
        parent := (i - 1) / 2
38
        if !h.data[i].Less(h.data[parent]) {
39
            break
40
        }
41
        h.data[i], h.data[parent] = h.data[parent], h.data[i]
42
        i = parent
43
    }
44
}
45

46
// 下沉：与较小子节点比较，比子大则交换
47
func (h *MinHeap[T]) siftDown(i int) {
48
    n := len(h.data)
49
    for {
50
        left, right := 2*i+1, 2*i+2
51
        smallest := i
52
        if left < n && h.data[left].Less(h.data[smallest]) {
53
            smallest = left
54
        }
55
        if right < n && h.data[right].Less(h.data[smallest]) {
56
            smallest = right
57
        }
58
        if smallest == i {
59
            break
60
        }
61
        h.data[i], h.data[smallest] = h.data[smallest], h.data[i]
62
        i = smallest
63
    }
64
}

1
// 最小堆，元素按 sortIndex 排序，id 用于 tie-break
2
interface HeapNode {
3
  sortIndex: number;
4
  id: number;
5
}
6

7
class MinHeap {
8
  private heap: HeapNode[] = [];
9
  private nextId = 0;
10

11
  push(sortIndex: number): void {
12
    const node: HeapNode = { sortIndex, id: this.nextId++ };
13
    this.heap.push(node);
14
    this.siftUp(this.heap.length - 1);
15
  }
16

17
  pop(): HeapNode | null {
18
    if (this.heap.length === 0) return null;
19
    const top = this.heap[0];
20
    const last = this.heap.pop()!;
21
    if (this.heap.length > 0) {
22
      this.heap[0] = last;
23
      this.siftDown(0);
24
    }
25
    return top;
26
  }
27

28
  peek(): HeapNode | null {
29
    return this.heap[0] ?? null;
30
  }
31

32
  get size(): number {
33
    return this.heap.length;
34
  }
35

36
  private siftUp(i: number): void {
37
    while (i > 0) {
38
      const parent = (i - 1) >>> 1;
39
      if (compare(this.heap[i], this.heap[parent]) >= 0) break;
40
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
41
      i = parent;
42
    }
43
  }
44

45
  private siftDown(i: number): void {
46
    const n = this.heap.length;
47
    while (true) {
48
      const left = 2 * i + 1;
49
      const right = 2 * i + 2;
50
      let smallest = i;
51
      if (left < n && compare(this.heap[left], this.heap[smallest]) < 0) smallest = left;
52
      if (right < n && compare(this.heap[right], this.heap[smallest]) < 0) smallest = right;
53
      if (smallest === i) break;
54
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
55
      i = smallest;
56
    }
57
  }
58
}
59

60
// 先比 sortIndex，相同则比 id（FIFO 顺序）
61
function compare(a: HeapNode, b: HeapNode): number {
62
  return a.sortIndex !== b.sortIndex
63
    ? a.sortIndex - b.sortIndex
64
    : a.id - b.id;
65
}