Skip to content

数据结构概览深入

综述高级数据结构:堆、平衡树、图及其时空权衡。

你将学到

  • 抽象数据类型与具体实现
  • 数据结构设计中的时空权衡
  • 动态结构的摊还界
  • 按操作特征选择数据结构

概念讲解

数据结构概览深入

数据结构是组织数据以高效支持特定操作的方式。艺术在于将数据结构与操作特征匹配——哪些操作频繁,哪些罕见。

抽象与具体

抽象数据类型(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 等等。

查看术语表

动手做项目

通过引导式项目应用所学,含起始代码与解决方案。

查看项目

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误