README_CN.md

data-structure-typed

English | 简体中文

一个生产就绪的 TypeScript 数据结构库，包含 Heap、Linked List、Deque、Trie、Graph、Red-Black Tree、TreeMap、TreeSet、SkipList、Segment Tree 等 — API 对齐 JavaScript 原生 Array、Map 和 Set。零依赖。类型安全。ES2025 Set 操作。O(log n) 排名和范围查询。

在 TypeScript/JavaScript 中寻找 TreeMap、TreeSet 或 PriorityQueue？ 熟悉的 API、集合操作、排名查询、有序访问 — 告别重复 Array.sort()。

📦 安装 • 🎮 Playground • ⚡ 快速开始 • 📖 文档 • 📋 API • 💡 示例 • ❓ FAQ

---

目录

1. 安装
2. Playground
3. 快速开始
4. 谁应该使用本库?
5. 为什么不直接用 Array 或 Map?
6. 核心特性
7. 数据结构
8. 文档
9. FAQ

---

📦 安装

npm i data-structure-typed

yarn add data-structure-typed

pnpm add data-structure-typed

子路径导入(支持 Tree-Shaking)

只导入你需要的 — 打包器会自动移除未使用的代码:

// 完整包 — 所有功能可用
import { RedBlackTree, Deque, HashMap } from 'data-structure-typed';

// 子路径 — 更小的包体积,只加载你需要的类别
import { RedBlackTree, TreeMap, AVLTree } from 'data-structure-typed/binary-tree';
import { Deque, Queue } from 'data-structure-typed/queue';
import { HashMap } from 'data-structure-typed/hash';
import { Heap, MinHeap } from 'data-structure-typed/heap';
import { Trie } from 'data-structure-typed/trie';
import { Stack } from 'data-structure-typed/stack';
import { DoublyLinkedList } from 'data-structure-typed/linked-list';
import { DirectedGraph } from 'data-structure-typed/graph';
import { Matrix } from 'data-structure-typed/matrix';
import { MinPriorityQueue } from 'data-structure-typed/priority-queue';

注意: 使用 "sideEffects": false 和现代打包器(Vite、Webpack 5、Rollup),即使是完整导入 from 'data-structure-typed' 也会进行 tree-shake。子路径导入让你拥有明确的控制权和更快的 IDE 自动补全。

独立包

也提供独立的 NPM 包:

npm i avl-tree-typed bst-typed heap-typed

---

🎮 Playground

立即尝试:

• Node.js TypeScript
• Node.js JavaScript
• React TypeScript
• NestJS

---

🎯 谁应该使用本库?

如果你正在用 TypeScript 构建排名集合、调度队列或排序数据结构, 请考虑使用 data-structure-typed 而不是手工编写的 Array 或 Map。

适用场景:

• 排行榜与排名 — 高效维护 top-K,无需重复排序
• 任务调度 — 优先级队列、有序执行、基于时间的操作
• 实时仪表板 — Grafana 风格的工作负载,即时查询
• 时间序列数据 — 有序插入 + 快速范围查询
• 搜索与自动补全 — 大规模前缀匹配
• 图论问题 — 路径查找、环检测、拓扑排序

---

⚡ 为什么不直接用 Array 或 Map?

使用场景	Array	Map	data-structure-typed
有序查找	❌ O(n)	❌ 无序	✅ O(log n)
指定位置插入	❌ O(n) shift	❌ 无位置	✅ O(log n)
排行榜 Top-K	❌ 重排序 O(n log n)	❌ 手动排序	✅ 即时
从前端移除	❌ O(n)	❌ 无出队	✅ O(1)
前缀搜索	❌ O(n*m)	❌ 不适用	✅ O(m + k)
熟悉的 API	✅ 有	✅ 有	✅ 相同

真实痛点

// ❌ 不使用 data-structure-typed
const queue = [1, 2, 3, ..., 100000
]
;
for (let i = 0; i < 100000; i++) {
  queue.shift();  // O(n) - 重新索引每个元素!
}
// 耗时: 2829ms ❌

// ✅ 使用 data-structure-typed (Deque)
const deque = new Deque([1, 2, 3, ..., 100000])
;
for (let i = 0; i < 100000; i++) {
  deque.shift();  // O(1) - 只移动指针
}
// 耗时: 5.83ms ✅
// **快 484 倍!**

---

🚀 性能 (TL;DR)

• 针对 V8 热路径优化 (查看 PERFORMANCE_CN.md 了解实测基准)

  • 重复 Array.shift() O(n) → Deque O(1)
  • 频繁更新 + 保持有序的工作流 → RedBlackTree O(log n) 操作
  • 如果每次更新后都必须保持有序,避免重复 Array.sort()

• 针对 V8 JIT 优化 (Node.js 18+, 现代浏览器)

• Tree-shakable ESM / CJS / legacy 构建

数据结构	测试用例	DST (ms)	Native (ms)	C++ (ms)	js-sdsl (ms)
Queue	1M push	26.93	23.83	1.70	27.59
Deque	1M push	9.77	26.81	1.76	7.79
DoublyLinkedList	100k push	5.70	2.40	5.70	1.90
SinglyLinkedList	100K unshift & shift	3.77	1958.39	4.80	-
PriorityQueue	100K add	4.00	-	1.05	4.96
TreeSet	1M add	995.72	-	462.00	677.58
TreeMap	1M set	978.72	-	512.00	623.23
TreeMultiSet	1M add (TreeMultiSet expanded iteration)	217.73	-	752.00	-
TreeMultiMap	1M add (TreeMultiMap bucketed)	366.19	-	731.00	-
RedBlackTree	1M get	99.24	-	52.97	-
BST	10K add randomly	5.50	-	-	-
BinaryTree	1K add randomly	9.77	-	-	-
HashMap	1M set	146.17	144.83	76.26	94.16
Trie	100K add	141.10	-	-	-
DirectedGraph	1K addVertex	0.05	-	-	-
Stack	1M push	46.38	30.28	1.65	32.38

📊 完整基准测试 → | 交互式报告 →

---

✨ 核心特性

🏠 统一 API

无需学习新 API。到处都使用 push、pop、map、filter 和 reduce。

// 所有线性结构使用相同的 4 个方法
const deque = new Deque([1, 2, 3]);
const queue = new Queue([1, 2, 3]);
const doublyLinkeList = new DoublyLinkedList([1, 2, 3]);
const singlyLinkedList = new SinglyLinkedList([1, 2, 3]);

// 它们都支持:
structure.push(item);          // 添加到末尾
structure.pop();               // 从末尾移除
structure.shift();             // 从开头移除
structure.unshift(item);       // 添加到开头

🛡️ 类型安全

开箱即用的完整泛型和严格 TypeScript 支持。

const tree = new RedBlackTree<number, string>();
tree.set(1, 'Alice');
tree.set(2, 'Bob');

// 类型安全的访问
const value = tree.get(1);  // 类型: string | undefined

✨ 零摩擦

随处可用。展开它 [...],循环它 for..of,即时转换。使用 toEntryFn/toElementFn 传入原始数据 — 无需预处理。

// 所有数据结构都支持迭代器协议
const tree = new RedBlackTree([5, 2, 8]);
const sorted = [...tree];              // 展开运算符
for (const item of tree) {
}           // for...of 循环
const set = new Set(tree);             // Set 构造器

// 直接传入原始数据
const map = new TreeMap(users, { toEntryFn: u => [u.id, u.name] });

🔄 处理原始数据

有原始对象?三种使用方式 — 根据你想存储的内容选择:

interface User {
  id: number;
  name: string;
}

const users: User[] = [
  { id: 3, name: 'Charlie' },
  { id: 1, name: 'Alice' },
  { id: 2, name: 'Bob' }
];

// 1. 提取字段 — 仅存储该字段
const ids = new TreeSet<number, User>(
  users,
  { toElementFn: u => u.id }
);
// [1, 2, 3] — 仅数字,不保留原始对象

// 2. 存储完整对象 — 按字段排序
const fullSet = new TreeSet<User>(
  users,
  { comparator: (a, b) => a.id - b.id }
);
// [{ id: 1, name: 'Alice' }, { id: 2, ... }, { id: 3, ... }]

// 3. 拆分为键值对 — 字段作为键,任意值
const map = new TreeMap<number, User, User>(
  users,
  { toEntryFn: u => [u.id, u] }
);
// map.get(1) → { id: 1, name: 'Alice' }

适用于所有数据结构 — 单值类型使用 toElementFn (Heap、Queue、Stack、LinkedList、Trie),键值类型使用 toEntryFn (TreeMap、HashMap、SkipList),任何排序结构使用 comparator。

---

💡 我应该何时考虑本库?

✅ 当你需要:

• Top-K / 排行榜查询而无需重复排序
• 同时实现插入顺序 + 查找性能
• 带快速位置访问的优先级队列
• 支持范围查询的时间序列数据
• Red-Black Tree / Heap 性能而无需学习新 API
• 直接传入原始对象 — 无需 .map() 预处理(JS/TS 中本库独有)

✅ 当你的代码有:

• 热路径中的 array.sort()(请求处理器、循环)
• 插入后的手动索引跟踪
• 大列表上的 Array.shift()(队列)
• 跨文件重复的自定义排序逻辑
• 需要有序的 Map
• 仅为重塑数据才调用 .map(),然后放入集合

---

🚀 快速开始: 30 秒

排行榜(排名集合)

import { RedBlackTree } from 'data-structure-typed';

// 降序比较器 — 最高分在前
const leaderboard = new RedBlackTree<number, string>([
  [100, 'Alice'],
  [85, 'Bob'],
  [92, 'Charlie']
], { comparator: (a, b) => b - a });

// 通过惰性迭代器获取 Top-2 — O(k log n),无数组拷贝
const iter = leaderboard.entries();
const { value: [topScore, topPlayer] } = iter.next();
console.log(`${topScore}: ${topPlayer}`); // 100: Alice

// 更新分数 — O(log n)
leaderboard.delete(85);
leaderboard.set(95, 'Bob');

// 范围查询 — 分数 90~100 的玩家, O(log n + k)
const scores90to100 = leaderboard.rangeSearch([90, 100]);
// [100, 95, 92] — 自动遵循树的顺序

// 对于 O(log n) top-k、排名和分页 → 参见下面的 Order-Statistic Tree

Order-Statistic Tree(排名查询)

import { RedBlackTree } from 'data-structure-typed';

const tree = new RedBlackTree<number, string>([
  [100, 'Alice'], [85, 'Bob'], [92, 'Charlie'],
  [78, 'Diana'], [95, 'Eve']
], { comparator: (a, b) => b - a, enableOrderStatistic: true });

// select(k) — 查找第 k 个元素, O(log n)
tree.getByRank(0);              // 100 (树顺序的第 1 个)
tree.getByRank(2);              // 92  (树顺序的第 3 个)

// rank(key) — 统计树顺序中 key 之前的元素数量, O(log n)
tree.getRank(92);               // 2 (树顺序中 92 之前有 2 个元素)

// rangeByRank — 分页, O(log n + k)
tree.rangeByRank(0, 2);      // [100, 95, 92] — 前 3 个

// 也适用于 TreeMap、TreeSet、TreeMultiMap、TreeMultiSet

任务队列(调度)

import { MaxPriorityQueue } from 'data-structure-typed';

const taskQueue = new MaxPriorityQueue<{priority: number; task: string}>([], {
  comparator: (a, b) => b.priority - a.priority
});

taskQueue.add({ priority: 5, task: 'Email' });
taskQueue.add({ priority: 9, task: 'Alert' });  // 即时优先级处理

const nextTask = taskQueue.pop();  // { priority: 9, task: 'Alert' }

集合操作 (ES2025)

import { TreeSet } from 'data-structure-typed';

const a = new TreeSet([1, 2, 3, 4, 5]);
const b = new TreeSet([3, 4, 5, 6, 7]);

[...a.union(b)];               // [1,2,3,4,5,6,7]
[...a.intersection(b)];        // [3,4,5]
[...a.difference(b)];          // [1,2]
[...a.symmetricDifference(b)]; // [1,2,6,7]
a.isSubsetOf(b);               // false

// 支持任意 Iterable — 原生 Set、数组、生成器
a.intersection(new Set([2, 4, 6]));  // TreeSet [2, 4]

快速队列 (FIFO)

import { Deque } from 'data-structure-typed';

const queue = new Deque([1, 2, 3, 4, 5]);
queue.shift();  // 从前端移除: O(1) 而非 O(n)
queue.push(6);  // 添加到后端: O(1)

---

📊 可用的数据结构

结构	使用场景	时间复杂度	NPM
RedBlackTree	有序集合、范围查询	O(log n)	npm
Heap / PriorityQueue	任务调度、top-K 元素	O(log n)	npm
Deque	快速前后操作	O(1)	npm
Trie	自动补全、前缀搜索	O(m+k)	npm
DirectedGraph	路径查找、DAG 算法	O(V+E)	npm
Stack	撤销/重做、表达式解析	O(1)	npm
LinkedList	动态大小、无索引移位	O(1)*	npm
AVLTree	比 RB-Tree 更严格的平衡	O(log n)	npm
SkipList	有序 KV、TreeMap 替代	O(log n) avg	—
SegmentTree	范围 sum/min/max/自定义查询	O(log n)	—
BinaryIndexedTree	前缀和、频率计数	O(log n)	—
Matrix	2D 网格运算	O(n²) add	—

👉 查看全部 20+ 结构 → | 完整 API 文档 →

---

📖 文档

不同使用场景

你的目标	从这里开始	下一步
学习概念	CONCEPTS_CN.md	GUIDES_CN.md
在项目中使用	GUIDES_CN.md	OVERVIEW_CN.md
查找 API	API 文档	PERFORMANCE_CN.md
性能问题	PERFORMANCE_CN.md	ARCHITECTURE_CN.md
框架集成	INTEGRATIONS_CN.md	GUIDES_CN.md
理解设计	ARCHITECTURE_CN.md	CONCEPTS_CN.md

文档文件

1. CONCEPTS_CN.md - 核心基础与理论

• 三大核心概念 (BST、平衡树、Heap)
• 13 个通俗语言解释
• 迭代器协议设计
• 5 个与原生 JavaScript 的对比
• 完整决策指南

2. API 文档 - 完整 API 参考 (TypeDoc)

• 完整的方法签名、参数、返回类型
• 每个方法的真实 @example 代码
• 继承层次和类型详情

3. OVERVIEW_CN.md - 数据结构概览

• 快速参考表
• 全部 20+ 结构及示例
• CRUD 操作
• 常用方法
• TypeScript 支持

4. ARCHITECTURE_CN.md - 设计与实现

• 设计理念与原则
• 解决的 3 大痛点
• 为什么 Deque 快 484 倍
• 迭代器协议设计
• 自平衡策略
• V8 JIT 优化

5. PERFORMANCE_CN.md - 基准测试与对比

• 性能总结
• 3 个真实场景
• 详细基准测试
• 何时使用什么
• 优化技巧

6. GUIDES_CN.md - 真实案例

• 4 种设计模式
• 5 个生产代码示例
• 常见错误
• 最佳实践

7. INTEGRATIONS_CN.md - 框架集成

• React 集成 (状态管理、排行榜)
• Express 集成 (LRU 缓存、限流)
• Nest.js 集成 (排名服务、任务队列)
• TypeScript 配置

---

💻 真实案例

LRU 缓存

class LRUCache<K, V> {
  private cache = new Map<K, V>();
  private order = new DoublyLinkedList<K>();

  get(key: K): V | null {
    if (!this.cache.has(key)) return null;
    // 移到末尾 (最近使用)
    // 利用 O(1) 操作实现高效
    return this.cache.get(key)!;
  }
}

排行榜

type Player = {
  id: string;
  name: string;
  score: number;
};

const seedPlayers: Player[] = [
  { id: 'player_01HZX4E8Q2K8Y3J9M7T1A6B3C4', name: 'Pablo', score: 65 },
  { id: 'player_01HZX4E9R6V2D8K1P0N5S4T7U8', name: 'Bunny', score: 10 },
  { id: 'player_01HZX4EA3M9Q7W1E2R8T6Y5U0I', name: 'Jeff', score: 99 },
];

class ScoreLeaderboard {
  private readonly byScore: RedBlackTree<number, Player, Player>;

  constructor(initialPlayers: Player[]) {
    this.byScore = new RedBlackTree<number, Player, Player>(initialPlayers, {
      isMapMode: false,// 使用"节点值"存储而非 Map 风格。
      toEntryFn: (player) => [player.score, player], // 将玩家对象转换为树条目: key = score, value = player.
    });
  }

  /**
   * 返回分数在给定范围内的玩家。
   * 支持元组 [min, max] 或 Range 对象以实现包含/排除边界。
   */
  public findPlayersByScoreRange(range: [number, number] | Range<number>): (Player | undefined)[] {
    return this.byScore.rangeSearch(range, (node) => node.value);
  }

  public upsertPlayer(player: Player) {
    return this.byScore.set(player.score, player);
  }
}

const leaderboard = new ScoreLeaderboard(seedPlayers);

console.log(leaderboard.findPlayersByScoreRange([65, 100]));

leaderboard.upsertPlayer({
  id: 'player_01HZX4EB7C4N2M9Q8R1T3Y6U5I',
  name: 'Alex',
  score: 80,
});

console.log(leaderboard.findPlayersByScoreRange(new Range(65, 100, true, true)));

消息队列

type Message = {
  id: string;
  type: string;
  payload: unknown;
  priority: 'urgent' | 'normal';
  createdAt: number;
  retryCount?: number;
};

class MessageQueue {
  private urgent = new Deque<Message>();
  private normal = new Deque<Message>();

  dequeue(): Message | null {
    return this.urgent.shift() || this.normal.shift();
  }
}

👉 更多示例在 GUIDES_CN.md

---

🎯 行业使用场景

📊 金融

• 价格排序的订单簿
• 实时投资组合排名
• 期权链排序

🎮 游戏

• 玩家排行榜
• 敌人优先级队列
• 游戏事件调度

📱 社交媒体

• 热门帖子 (top-K)
• 信息流排序
• 通知调度

🏥 医疗

• 患者优先级队列
• 预约调度
• 医疗记录组织

🛒 电商

• 产品价格范围
• 库存管理
• 订单调度

---

✨ 开发者喜爱的原因

痛点	解决方案
重复排序拖慢代码	TreeSet 自动维护顺序
循环中 Array.shift 超时	Deque O(1) shift 而非 O(n)
学习不同 API	所有结构都使用 push/pop/shift/unshift
类型安全噩梦	完整 TypeScript 泛型支持
浏览器兼容性问题	随处可用: Node、浏览器、CDN

---

📦 你将获得

✅ 20+ 数据结构 (生产就绪) ✅ 50+ 代码示例 (真实模式) ✅ 完整 TypeScript 支持 (严格类型) ✅ 性能基准测试 (484 倍加速) ✅ 框架集成 (React、Express、Nest.js) ✅ 6 个核心文档文件 (2500+ 行)

---

🚀 开始使用

步骤 1: 安装

npm i data-structure-typed

步骤 2: 导入

import { RedBlackTree, Deque, MaxPriorityQueue } from 'data-structure-typed';

步骤 3: 使用

const tree = new RedBlackTree([5, 2, 8]);
console.log([...tree]);  // [2, 5, 8] - 自动排序!

📊 对比图表

需要频繁头/尾操作?
  → Deque (O(1) shift/unshift/push/pop)

需要排序 + 快速查找?
  → RedBlackTree (O(log n) 保证)

需要最高/最低优先级?
  → Heap/PriorityQueue (O(log n) add/remove)

需要前缀/文本匹配?
  → Trie (O(m+k) 其中 m=前缀)

需要图论操作?
  → DirectedGraph/UndirectedGraph

需要数组上的范围查询 (sum/min/max)?
  → SegmentTree (任意合并操作) 或 BinaryIndexedTree (仅前缀和)

需要有序键值对且 API 与 TreeMap 相同?
  → SkipList (O(log n) avg, 概率平衡)

否则?
  → 使用 Array (最简单的情况)

---

🤝 贡献

发现 bug?有建议? 提出 issue

---

📄 许可

MIT

---

📚 完整文档结构

README.md (本文件)
docs/
├── CONCEPTS_CN.md (理论与基础)
├── OVERVIEW_CN.md (数据结构概览)
├── ARCHITECTURE_CN.md (设计原则)
├── PERFORMANCE_CN.md (基准测试)
├── GUIDES_CN.md (真实案例)
└── INTEGRATIONS_CN.md (框架指南)

---

🎓 了解更多

刚开始? → 快速开始

需要概念? → CONCEPTS_CN.md

想构建? → GUIDES_CN.md

需要 API? → API 文档 | 概览

关心性能? → PERFORMANCE_CN.md

框架问题? → INTEGRATIONS_CN.md

---

准备好加速你的 TypeScript 数据结构了吗? 现在开始 →

---

❓ FAQ

JavaScript 有 TreeMap 或 TreeSet 吗?

原生没有。JavaScript 的 Map 和 Set 是基于哈希的(无序)。本库提供由 Red-Black Tree 支持的 TreeMap 和 TreeSet — 提供有序迭代、floor/ceiling/higher/lower 查找,以及 getRank/getByRank/rangeByRank 查询。

何时应该使用 Heap 而不是排序数组?

当你需要重复访问最小或最大元素时。排序数组每次都是 O(n log n); Heap 提供 O(log n) 插入和 O(1) 访问顶部元素。对于优先级队列、top-k 问题和调度,使用 Heap、MinHeap 或 MaxHeap。

本库支持排名和范围查询吗?

是的。在任何基于树的结构(RedBlackTree、TreeMap、TreeSet 等)上启用 { enableOrderStatistic: true }:

• getRank(key) — 树顺序中这个 key 之前有多少元素
• getByRank(k) — 获取位置 k 的元素
• rangeByRank(start, end) — 获取两个位置之间的所有元素

对于有序操作,它比原生数组快吗?

对于有序插入 + 查找: 是的。数组插入到有序位置是 O(n) (移动元素)。Red-Black Tree 插入是 O(log n)。对于 10,000+ 元素,差异显著。查看 PERFORMANCE_CN.md 了解基准测试。

我可以在 React / Node.js / 浏览器中使用吗?

可以。本库提供 ESM、CJS 和 UMD 构建。它可在 Node.js、浏览器、React、Vue、Angular、Next.js 和任何 JavaScript 运行时中使用。零依赖意味着无兼容性问题。

包含哪些数据结构?

Heap、MinHeap、MaxHeap、Priority Queue、Deque、Queue、Stack、Linked List (Singly / Doubly)、Red-Black Tree、AVL Tree、BST、TreeMap、TreeSet、TreeMultiMap、TreeMultiSet、SkipList、Trie、HashMap、Graph (Directed / Undirected)、Segment Tree、Binary Indexed Tree (Fenwick Tree)、Matrix。查看完整列表。

本库生产就绪吗?

是的。2600+ 测试,99%+ 代码覆盖率,零依赖,并在生产环境中使用。每次发布都通过类型检查、lint 和完整测试套件。

与 js-sdsl 或其他库相比如何?

data-structure-typed 提供更多数据结构(20+)、跨所有结构的统一类似 Array 的 API、tree-shakeable 子路径导出和积极维护。查看 PERFORMANCE_CN.md 了解基准对比。

我可以在不先转换的情况下传入原始数据吗?

可以。三种模式:

• toElementFn — 提取字段,仅存储该字段 (TreeSet、Heap、Queue、Stack、LinkedList、Trie)
• comparator — 存储完整对象,按字段排序 (所有排序结构)
• toEntryFn — 拆分为键值对 (TreeMap、HashMap、SkipList)

查看原始数据部分了解示例。

包体积是多少?

UMD bundle: ~143KB minified。使用子路径导入(如 data-structure-typed/heap),你只加载需要的 — Stack 小至 18KB,Heap 30KB。sideEffects: false 启用完整 tree-shaking。