@siroi/min-heap - 高性能小顶堆数据结构

通用、高效的小顶堆（Min-Heap）数据结构实现，基于 TypeScript 开发，支持自定义比较逻辑，适用于优先级队列、Top-K 问题等场景

✨ 核心特性

✅ 类型安全：完整的 TypeScript 类型定义，支持泛型适配任意数据类型
✅ 灵活扩展：支持自定义比较函数，解耦数据结构与业务逻辑
✅ 高效性能：O(1) 获取堆顶元素，O(log n) 插入/删除操作
✅ 简洁 API：直观的方法命名，低学习成本
✅ ES 模块兼容：原生支持 ES Module，适配现代项目架构
✅ 零依赖：无额外依赖，体积小巧

📦 安装

npm install @siroi/min-heap
# 或
yarn add @siroi/min-heap
# 或
pnpm add @siroi/min-heap

🚀 快速开始

基本用法

import { MinHeap } from '@siroi/min-heap';

// 创建一个数值小顶堆
const numberHeap = new MinHeap<number>((a, b) => a - b);

// 插入元素
numberHeap.insert(5);
numberHeap.insert(3);
numberHeap.insert(8);
numberHeap.insert(1);

// 获取最高优先级元素
console.log(numberHeap.peekTop()); // 1
console.log(numberHeap.extractTop()); // 1
console.log(numberHeap.extractTop()); // 3

优先级任务队列

import { MinHeap } from '@siroi/min-heap';

interface Task {
  id: string;
  name: string;
  priority: number; // 数值越小优先级越高
  execute: () => void;
}

// 创建任务优先级队列
const taskQueue = new MinHeap<Task>();

// 添加任务
taskQueue.insert({
  id: 'task1',
  name: '数据加载',
  priority: TaskPriority.NORMAL,
  execute: () => console.log('加载数据...')
});

taskQueue.insert({
  id: 'task2', 
  name: 'UI渲染',
  priority: TaskPriority.HIGH, // 更高优先级
  execute: () => console.log('渲染界面...')
});

// 按优先级执行任务
while (!taskQueue.isEmpty()) {
  const task = taskQueue.extractTop();
  task?.execute();
}

// 输出:
// 渲染界面...
// 加载数据...
// 创建任务优先级队列

Top-K 问题

import { MinHeap } from '@siroi/min-heap';

/**
 * 从数组中找出 Top-K 最大元素
 * @param arr 原始数组
 * @param k 要获取的最大元素个数
 */
function findTopK<T>(arr: T[], k: number, compare: (a: T, b: T) => number): T[] {
  const heap = new MinHeap<T>(compare);
  
  // 先插入前 k 个元素
  for (let i = 0; i < k; i++) {
    heap.insert(arr[i]);
  }
  
  // 后续元素：若大于堆顶，则替换堆顶
  for (let i = k; i < arr.length; i++) {
    const top = heap.peekTop();
    if (top && compare(arr[i], top) > 0) {
      heap.extractTop();
      heap.insert(arr[i]);
    }
  }
  
  // 提取结果（堆中元素即为 Top-K 最大元素）
  const result: T[] = [];
  while (!heap.isEmpty()) {
    result.push(heap.extractTop()!);
  }
  return result.reverse(); // 反转后按降序排列
}

// 示例：找出 Top-3 最大数值
const numbers = [12, 3, 8, 15, 7, 20, 5];
const top3 = findTopK(numbers, 3, (a, b) => a - b);
console.log(top3); // [20, 15, 12]

📚 API 参考

构造函数

new MinHeap<T>(compare?: (a: T, b: T) => number)

实例方法

1. isEmpty(): boolean

• 说明：检查堆是否为空
• 返回值：true 表示堆为空，false 表示非空
• 时间复杂度：O (1)

2. insert(element: T): void

• 说明：插入元素到堆中
• 参数：element - 待插入的元素
• 抛出错误：当比较函数执行失败时（如元素缺少必要属性）
• 时间复杂度：O (log n)

3. extractTop(): T | undefined

• 说明：取出并返回堆顶元素（优先级最高）
• 返回值：堆顶元素，堆为空时返回 undefined
• 时间复杂度：O (log n)

4. peekTop(): T | undefined

• 说明：查看堆顶元素（不删除）
• 返回值：堆顶元素，堆为空时返回 undefined
• 时间复杂度：O (1)

5. clear(): void

• 说明：清空堆中所有元素
• 时间复杂度：O (1)（垃圾回收除外）

6. forEach(callback: (element: T, index: number) => void, thisArg?: any): void

• 说明：遍历堆中所有元素（按数组存储顺序，非优先级顺序）
• 参数：
  • callback：遍历回调函数，接收元素和索引
  • thisArg：可选，回调函数的 this 指向
• 注意：遍历过程中禁止修改堆结构（插入 / 删除元素）
• 时间复杂度：O (n)

7. findIndex(predicate: (element: T) => boolean): number

• 说明：线性查找元素索引
• 参数：predicate - 查找条件函数
• 返回值：找到的元素索引，未找到返回 -1
• 性能警告：时间复杂度 O (n)，不适合高频调用
• 时间复杂度：O (n)

8. deleteAt(index: number): T | undefined

• 说明：删除指定索引的元素
• 参数：index - 待删除元素的索引
• 返回值：被删除的元素，索引无效时返回 undefined
• 时间复杂度：O (log n)

❓ 常见问题

Q: 为什么选择小顶堆而不是普通数组？ A: 小顶堆在频繁获取最大/最小值的场景下性能显著优于数组，特别是当数据量较大时。普通数组的排序操作是 O(n log n)，而堆的插入和提取操作都是 O(log n)。

Q: 能否用于浏览器环境？ A: 是的！本库完全兼容现代浏览器环境，已使用 ES 模块标准打包，可直接在支持 ES 模块的浏览器中使用。

Q: 如何实现最大堆？ A: 通过反转比较函数符号：

// 最大堆：数值越大优先级越高
const maxHeap = new MinHeap<number>((a, b) => b - a);