npm package: @siroi/min-heap
Description: 数据结构-最小堆
Author: siroi
Latest version: 1.0.1

@siroi/min-heap - 高性能小顶堆数据结构

[![npm version](https://img.shields.io/npm/v/@siroi/min-heap.svg)](https://www.npmjs.com/package/@siroi/min-heap)

通用、高效的小顶堆（Min-Heap）数据结构实现，基于 TypeScript 开发，支持自定义比较逻辑，适用于优先级队列、Top-K 问题等场景

## ✨ 核心特性
✅ **类型安全**：完整的 TypeScript 类型定义，支持泛型适配任意数据类型  
✅ **灵活扩展**：支持自定义比较函数，解耦数据结构与业务逻辑  
✅ **高效性能**：O(1) 获取堆顶元素，O(log n) 插入/删除操作  
✅ **简洁 API**：直观的方法命名，低学习成本  
✅ **ES 模块兼容**：原生支持 ES Module，适配现代项目架构  
✅ **零依赖**：无额外依赖，体积小巧

## 📦 安装
```bash
npm install @siroi/min-heap
# 或
yarn add @siroi/min-heap
# 或
pnpm add @siroi/min-heap
```
## 🚀 快速开始
### 基本用法
```typescript
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
```


### 优先级任务队列
```typescript
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 问题
```typescript
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 参考
### 构造函数
```typescript
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: 通过反转比较函数符号：
```typescript
// 最大堆：数值越大优先级越高
const maxHeap = new MinHeap<number>((a, b) => b - a);
```