Heap

堆数据结构，支持最小堆和最大堆。

函数签名

function createHeap<T>(
  type?: 'min' | 'max',
  compare?: (a: T, b: T) => number
): Heap<T>

interface Heap<T> {
  insert(value: T): void
  extract(): T | undefined
  peek(): T | undefined
  size(): number
  isEmpty(): boolean
  clear(): void
  toArray(): T[]
}

API 说明

insert(value): void

插入元素。

时间复杂度：O(log n)

extract(): T | undefined

移除并返回堆顶元素。

时间复杂度：O(log n)

使用示例

import { createHeap } from '@shared/functions/data-structures/Heap'

// 最小堆
const minHeap = createHeap<number>('min')
minHeap.insert(5)
minHeap.insert(3)
minHeap.insert(7)
console.log(minHeap.extract())  // 3

// 最大堆
const maxHeap = createHeap<number>('max')
maxHeap.insert(5)
maxHeap.insert(3)
maxHeap.insert(7)
console.log(maxHeap.extract())  // 7

应用场景

1. 优先队列：任务调度
2. 堆排序：排序算法
3. Top K 问题：找前 K 大/小元素
4. 中位数维护：动态求中位数