数据结构概览深入
综述高级数据结构:堆、平衡树、图及其时空权衡。
你将学到
- 抽象数据类型与具体实现
- 数据结构设计中的时空权衡
- 动态结构的摊还界
- 按操作特征选择数据结构
概念讲解
数据结构概览深入
数据结构是组织数据以高效支持特定操作的方式。艺术在于将数据结构与操作特征匹配——哪些操作频繁,哪些罕见。
抽象与具体
抽象数据类型(ADT)指定可用操作而不说明如何实现。具体实现决定如何实现。同一 ADT 可有多种不同性能特征的实现。
操作特征
选择数据结构前,问:我将执行哪些操作,频率如何?如果主要插入很少搜索,链表足够。如果持续搜索,哈希表或平衡树更好。如果需要有序遍历,树优于哈希表。
关键权衡
数组与链表:数组提供 O(1) 随机访问但中间插入删除为 O(n)。链表在已知位置提供 O(1) 插入删除但访问为 O(n)。哈希表与树:哈希提供 O(1) 平均查找但无序。树提供 O(log n) 查找且有序和范围查询。堆与有序数组:堆提供 O(log n) 插入和 O(1) 最值但无任意查找。
摊还结构
动态数组、链式哈希表和并查集都有摊还保证。单独操作可能慢,但多次操作的平均很快。
示例代码
// Binary heap (min-heap) - O(log n) insert/extract
class MinHeap {
constructor() { this.h = []; }
push(x) {
this.h.push(x);
let i = this.h.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.h[p] <= this.h[i]) break;
[this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p;
}
}
pop() {
const top = this.h[0]; const last = this.h.pop();
if (this.h.length > 0) {
this.h[0] = last; let i = 0; const n = this.h.length;
while (true) {
let s = i, l = 2*i+1, r = 2*i+2;
if (l < n && this.h[l] < this.h[s]) s = l;
if (r < n && this.h[r] < this.h[s]) s = r;
if (s === i) break;
[this.h[i], this.h[s]] = [this.h[s], this.h[i]]; i = s;
}
}
return top;
}
}
const heap = new MinHeap();
[5, 3, 8, 1, 9, 2].forEach(x => heap.push(x));
console.log(heap.pop(), heap.pop(), heap.pop());
最小堆维护堆性质:每个父节点 <= 其子节点。push 上浮,pop 将最后元素交换到根并下沉。两者均为 O(log n)。
动手试一试
- JSON Formatter
JSON 对象和数组是数据结构——观察不同组织如何影响访问模式。
常见错误
错误写法
需要随机访问时使用链表。
正确做法
链表按索引访问为 O(n)。如果频繁按位置访问,使用数组。
错误写法
忘记哈希表顺序未定义。
正确做法
不要依赖普通哈希表的插入顺序。如需有序遍历,使用树映射或插入有序映射。
查阅不认识的术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
动手做项目
通过引导式项目应用所学,含起始代码与解决方案。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。