常用数据结构

  • 数组(Array)
  • 栈( Stack)
  • 队列(Queue)
  • 链表( Linked List)
  • 树( Tree)
  • 图(Graph)
  • 堆(Heap)

  • 散列表(Hash)

    栈

    image.png
    image.png
    image.png

    栈的应用场景

  • 需要后进先出的场景。

  • 比如：十进制转二进制、判断字符串的括号是否有效、函数调用堆栈…

image.png
image.png

image.png

队列

image.png
image.png

队列的应用场景

  • 需要先进先出的场景。
  • 比如：食堂排队打饭、JS异步中的任务队列、计算最近请求次数。

image.png

image.png

优先队列（PriorityQueue）

实现机制：

  • Heap (Binary、Binomial、Fibonacci)
  • Binary Search Tree

链表

  • 链表是一种物理结构（非逻辑结构)，类似于数组
  • JS 中没有链表，但可以用 Object 模拟实现
  • 数组需要一段连续的内存区间（连续即表示有序），而链表是零散的（数据可以存在任意地方，用指针连接）
  • 链表节点的数据结构 {value,next?,prev?}

单向链表

使用 next 指针

双向链表

使用 next + prev 指针

链表VS数组

  • 都是有序结构
  • 数组：增删非首尾元素时往往需要移动元素。查询快O(1)，新增和删除慢O(n)。因为数组只要知道索引就能快速找到对应的数据，而链表上的数据不是连续的，需要一个个的去比较。
  • 链表：查询慢O(n)，新增和删除快O(1)。增删非首尾元素，不需要移动元素，只需要更改 next 的指向即可。

链表和数组，哪个实现队列更快？

  • 虽然数组也能实现队列，但是有性能问题的。数组元素入队列的话，需要 O(1)，出队列的话，需要 O(n)。而链表入列和出列都是 O(1)。
  • 空间复杂度都是O(n)
  • add 时间复杂度：链表O(1)；数组O(1)
  • delete 时间复杂度：链表O(1);数组O(n)

题目

删除链表中的节点

image.png

反转链表

image.png
image.png

两数相加

image.png

删除排序链表中的重复元素

image.png

环形链表

image.png
image.png
image.png

集合

  • 一种无序且唯一的数据结构。
  • ES6 中就有集合，如：Set。
  • 集合的常用操作：去重、判断某元素是否在集合中、求交集

HashSet

  • HashTable
  • Hash Function
  • Collisions

TreeSet

  • HashTable
  • Hash Function
  • Collisions

题目

两个数组的交集

image.png

散列表/哈希表/字典/映射

散列表/哈希表

  • 维基百科定义：散列表（HashTable，也叫哈希表 HashMap ），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名 x 到首字母 F(x)的一个函数关系）， 在首字母为 W 的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则 F()， 存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。
    • HashTable：哈希表，又称散列表，英文名为Hash Table。实质上是一种对数组进行了扩展的数据结构，可以说哈希表是在数组支持下标直接索引数据(value)的基础上进行优化并尽可能在常数时间内对数据进行增、删、改、查等操作。
    • Hash Function：散列函数又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（hash values，hash codes，hash sums，或 hashes）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。
    • Collisions：不管什么数据结构，存储空间都是有限的，也就是说存储的数据量是一定的，那么当要存储的数据量超过这一数据结构当前容量(capacity)，就会发生至少两个键值对应在哈希表的同一个位置。比如，哈希表中有十个位置，那么现在要存放十一个数字到十个位置，即至少有两个数字会存放到同一个位置，这也就是鸽巢原理(抽屉原理)。

字典/映射

  • 映射（Map）/字典(Dictionary)也是一种的以 键-值对 形式存储唯一值的逻辑数据结构，JS 中对应的物理结构：Object、Map。

字典/映射和散列表/哈希表的区别

  • 散列表是实现字典的方式之一：字典注重的是“一个键值(key)对应一个值(value)“的概念，而字典的实现既可以是二维数组，也可以是哈希表；

题目

两个数组的交集

image.png

有效的括号

image.png

括号生成

  1. const generateParenthesis = function (n) {
  2.     const set = new Set();
  3.     const fn = (left, right, n, result) => {
  4.         if (left === n && right === n) {
  5.             set.add(result);
  6.             return
  7.         }
  8.         if (left < n) {
  9.              fn(left + 1, right, n, result + "(");
  10.         }
  11.         if (right < n && left > right) {
  12.              fn(left, right + 1, n, result + ")");
  13.         }
  14.     }
  15.     fn(0, 0, n, '');
  16.     return Array.from(set);
  17. }

两数之和

image.png

无重复字符的最长子串

image.png
image.png
image.png

最小覆盖子串

image.png

image.png
image.png
image.png

有效的字母异位词

  • 异位词：两个字符串长度一致，字符串里面用到的字母一致，唯一不同的是顺序。如：”anagram”、”nagaram”。
  • 方法一：将两个字符串排序，排序好后直接比较是否相等；
  • 方法二：使用 map 存储每个字母并记录每个字母出现的次数，然后比对两个 map；

树

  • 一种分层数据的抽象模型。
  • 前端工作中常见的树包括：DOM树、级联选择、树形控件.…

image.png

  • JS中没有树，但是可以用 Object 和 Array 构建树。
  • 树的常用操作：深度/广度优先遍历、先/中/后序遍历。

image.png

深度/广度优先遍历

image.png

深度优先遍历算法口诀

  • 访问根节点。
  • 对根节点的 children 挨个进行深度优先遍历。
  1. const tree = {
  2.     val: 'a',
  3.     children: [
  4.         {
  5.             val: 'b',
  6.             children: [
  7.                 {
  8.                     val: 'd',
  9.                     children: [],
  10.                 },
  11.                 {
  12.                     val: 'e',
  13.                     children: [],
  14.                 }
  15.             ],
  16.         },
  17.         {
  18.             val: 'c',
  19.             children: [
  20.                 {
  21.                     val: 'f',
  22.                     children: [],
  23.                 },
  24.                 {
  25.                     val: 'g',
  26.                     children: [],
  27.                 }
  28.             ],
  29.         }
  30.     ],
  31. };
  33. const dfs = (root) => {
  34.     console.log(root.val);
  35.     root.children.forEach(dfs);
  36. };
  38. dfs(tree);

广度优先遍历算法口诀

  • 新建一个队列，把根节点入队；
  • 把队头出队并访问；
  • 把队头的 children 挨个入队；
  • 重复第二、三步，直到队列为空；
  1. const tree = {
  2.     val: 'a',
  3.     children: [
  4.         {
  5.             val: 'b',
  6.             children: [
  7.                 {
  8.                     val: 'd',
  9.                     children: [],
  10.                 },
  11.                 {
  12.                     val: 'e',
  13.                     children: [],
  14.                 }
  15.             ],
  16.         },
  17.         {
  18.             val: 'c',
  19.             children: [
  20.                 {
  21.                     val: 'f',
  22.                     children: [],
  23.                 },
  24.                 {
  25.                     val: 'g',
  26.                     children: [],
  27.                 }
  28.             ],
  29.         }
  30.     ],
  31. };
  33. const bfs = (root) => {
  34.     const q = [root];
  35.     while (q.length > 0) {
  36.         const n = q.shift();
  37.         console.log(n.val);
  38.         n.children.forEach(child => {
  39.             q.push(child);
  40.         });
  41.     }
  42. };
  44. bfs(tree);

二叉树

  • 树中每个节点最多只能有两个子节点（为什么不能有三个及以上的子节点？因为二分法，可以快速的查询树）；
  • 在 JS 中通常用 Object 来模拟二叉树；

二叉树的遍历方式

  • 前序遍历：root->left->right
  • 中序遍历：left->root->right
  • 后序遍历：left->right->root

先序遍历算法口诀

image.png

  1. const bt = {
  2.     val: 1,
  3.     left: {
  4.         val: 2,
  5.         left: {
  6.             val: 4,
  7.             left: null,
  8.             right: null,
  9.         },
  10.         right: {
  11.             val: 5,
  12.             left: null,
  13.             right: null,
  14.         },
  15.     },
  16.     right: {
  17.         val: 3,
  18.         left: {
  19.             val: 6,
  20.             left: null,
  21.             right: null,
  22.         },
  23.         right: {
  24.             val: 7,
  25.             left: null,
  26.             right: null,
  27.         },
  28.     },
  29. };
  31. const preorder = (root) => {
  32.     if (!root) { return; }
  33.     console.log(root.val);
  34.     preorder(root.left);
  35.     preorder(root.right);
  36. };
  38. // 非递归版本
  39. // const preorder = (root) => {
  40. //     if (!root) { return; }
  41. //     const stack = [root];
  42. //     while (stack.length) {
  43. //         const n = stack.pop();
  44. //         console.log(n.val);
  45. //                  // 栈的执行顺序是后进先出
  46. //         if (n.right) stack.push(n.right);
  47. //         if (n.left) stack.push(n.left);
  48. //     }
  49. // };
  51. preorder(bt);

中序遍历算法口诀

image.png

  1. const inorder = (root) => {
  2.     if (!root) { return; }
  3.     inorder(root.left);
  4.     console.log(root.val);
  5.     inorder(root.right);
  6. };
  8. // 非递归版本
  9. // const inorder = (root) => {
  10. //     if (!root) { return; }
  11. //     const stack = [];
  12. //     let p = root;
  13. //     while (stack.length || p) {
  14. //         while (p) {
  15. //             stack.push(p);
  16. //             p = p.left;
  17. //         }
  18. //         const n = stack.pop();
  19. //         console.log(n.val);
  20. //         p = n.right;
  21. //     }
  22. // };
  24. inorder(bt);

后序遍历算法口诀

image.png

  1. const postorder = (root) => {
  2.     if (!root) { return; }
  3.     postorder(root.left);
  4.     postorder(root.right);
  5.     console.log(root.val);
  6. };
  8. // 非递归版本
  9. // const postorder = (root) => {
  10. //     if (!root) { return; }
  11. //     const outputStack = [];
  12. //     const stack = [root];
  13. //     while (stack.length) {
  14. //         const n = stack.pop();
  15. //         outputStack.push(n);
  16. //         if (n.left) stack.push(n.left);
  17. //         if (n.right) stack.push(n.right);
  18. //     }
  19. //     while(outputStack.length){
  20. //         const n = outputStack.pop();
  21. //         console.log(n.val);
  22. //     }
  23. // };
  25. postorder(bt);

二叉搜索树

image.png
image.png

  • 搜索树中的某个节点时，只需要比较当前树的根节点的大小，如果当前值小于根节点，那么只需要搜索左侧的子树就行；如果大于根节点，只需要搜索右侧的子树就行。

题目

二叉树的最大深度

image.png

二叉树的最小深度

image.png

二叉树的层序遍历

image.png
image.png

二叉树的中序遍历

路径总和

image.png

验证二叉搜索树

二叉树的最近公共祖先

二叉搜索树的最近公共祖先

字典树

image.png

  • 核心思想：空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
  • 特点：
    • 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
    • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
    • 每个节点的所有子节点包含的字符都不相同。

应用场景

image.png

题目

实现 Trie (前缀树)

单词搜索

单词搜索 II

并查集

题目

岛屿数量

省份数量

图

  • JS中没有图，但是可以用 Object 和 Array 构建图；
  • 图的表示法：邻接矩阵、邻接表、关联矩阵；
  • 用了表示节点之间的关系；

image.png
image.png

image.png
image.png

图的深度优先遍历算法口诀

image.png

  1. const graph = {
  2.     0: [1, 2],
  3.     1: [2],
  4.     2: [0, 3],
  5.     3: [3]
  6. };
  7. const visited = new Set();
  8. const dfs = (n) => {
  9.     console.log(n);
  10.     visited.add(n);
  11.     graph[n].forEach(c => {
  12.         if(!visited.has(c)){
  13.             dfs(c);
  14.         }
  15.     });
  16. };
  18. dfs(2);

图的广度优先遍历算法口诀

image.png

  1. const graph = {
  2.     0: [1, 2],
  3.     1: [2],
  4.     2: [0, 3],
  5.     3: [3]
  6. };
  7. const visited = new Set();
  8. const q = [2];
  9. while (q.length) {
  10.     const n = q.shift();
  11.     console.log(n);
  12.     visited.add(n);
  13.     graph[n].forEach(c => {
  14.         if (!visited.has(c)) {
  15.             q.push(c);
  16.         }
  17.     });
  18. }

题目

有效数字

image.png

堆

image.png

完全二叉树

  • 堆是一种特殊的完全二叉树，如果一棵树丛根节点一直到叶子节点为止，每个节点（除了叶子节点外）都有两个子节点，那么我们称之为满二叉树，而如果有部分子节点只有0-1个子节点，那么我们称之为完全二叉树。

image.png

  • 最大堆：父节点>=子节点，假设三个节点构成一棵子树，父节点的值一定大于子节点。
  • 最小堆：父节点<=子节点

image.png

堆的节点查找公式

  • 数组的首元素就是堆顶元素；

image.png

堆的应用

  • 堆能高效、快速地找出最大值和最小值，时间复杂度：0(1)。
  • 用来找出第 K 个最大（小）元素（常见的算法题就是用堆来解决的）。
  • React Fiber 中的任务优先级排列方式就是通过最小堆算法实现的。

实现最小堆算法

https://github.com/yjdjiayou/react-scheduler-easy/blob/main/scheduler/src/SchedulerMinHeap.js

插入

image.png

  1. class MinHeap {
  2.     constructor() {
  3.         this.heap = [];
  4.     }
  6.        swap(i1, i2) {
  7.         // const tmp = this.heap[i1];
  8.         // this.heap[i1] = this.heap[i2];
  9.         // this.heap[i2] = tmp;
  10.         [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]
  11.     }
  13.     getParentIndex(i) {
  14.         // return Math.floor((i - 1) / 2);
  15.         // 位运算：将二进制向右移一位，也就相当于除 2
  16.         return (i - 1) >> 1;
  17.     }
  19.     // O(logn)
  20.     shiftUp(index) {
  21.         if (index === 0) return;
  22.         const parentIndex = this.getParentIndex(index);
  23.         if (this.heap[parentIndex] > this.heap[index]) {
  24.             // this.swap(parentIndex, index);
  25.             [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]]
  26.             this.shiftUp(parentIndex);
  28.         }
  29.     }
  31.     insert(val) {
  32.         this.heap.push(val);
  33.         this.shiftUp(this.heap.length - 1);
  34.     }
  35. }
  38. const a = new MinHeap();
  39. a.insert(3)
  40. a.insert(2)
  41. a.insert(1)
  42. console.log(a.heap);

image.png

删除堆顶

  1. class MinHeap {
  2.     constructor() {
  3.         this.heap = [];
  4.     }
  6.     swap(i1, i2) {
  7.         // const tmp = this.heap[i1];
  8.         // this.heap[i1] = this.heap[i2];
  9.         // this.heap[i2] = tmp;
  10.         [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]
  11.     }
  13.     getParentIndex(i) {
  14.         // return Math.floor((i - 1) / 2);
  15.         // 位运算：将二进制向右移一位，也就相当于除 2
  16.         return (i - 1) >> 1;
  17.     }
  19.     getLeftIndex(i) {
  20.         return i * 2 + 1;
  21.     }
  23.     getRightIndex(i) {
  24.         return i * 2 + 2;
  25.     }
  26.     // O(logn)
  27.     shiftUp(index) {
  28.         if (index === 0) return;
  29.         const parentIndex = this.getParentIndex(index);
  30.         if (this.heap[parentIndex] > this.heap[index]) {
  31.             this.swap(parentIndex, index);
  32.             this.shiftUp(parentIndex);
  33.         }
  34.     }
  35.     // O(logn)
  36.     shiftDown(index) {
  37.         const leftIndex = this.getLeftIndex(index);
  38.         const rightIndex = this.getRightIndex(index);
  39.         if (this.heap[leftIndex] < this.heap[index]) {
  40.             this.swap(leftIndex, index);
  41.             this.shiftDown(leftIndex);
  42.         }
  43.         if (this.heap[rightIndex] < this.heap[index]) {
  44.             this.swap(rightIndex, index);
  45.             this.shiftDown(rightIndex);
  46.         }
  47.     }
  49.     insert(val) {
  50.         this.heap.push(val);
  51.         this.shiftUp(this.heap.length - 1);
  52.     }
  54.     pop() {
  55.         this.heap[0] = this.heap.pop();
  56.         this.shiftDown(0);
  57.     }
  58. }
  60. const a = new MinHeap();
  61. a.insert(3)
  62. a.insert(2)
  63. a.insert(4)
  64. a.insert(5)
  65. a.insert(1)
  66. console.log(a.heap);// [ 1, 2, 4, 5, 3 ]
  67. a.pop()
  68. console.log(a.heap);// [ 2, 3, 4, 5 ]

获取堆顶元素

  1. class MinHeap {
  2.     constructor() {
  3.         this.heap = [];
  4.     }
  6.     swap(i1, i2) {
  7.         // const tmp = this.heap[i1];
  8.         // this.heap[i1] = this.heap[i2];
  9.         // this.heap[i2] = tmp;
  10.         [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]
  11.     }
  13.     getParentIndex(i) {
  14.         // return Math.floor((i - 1) / 2);
  15.         // 位运算：将二进制向右移一位，也就相当于除 2
  16.         return (i - 1) >> 1;
  17.     }
  19.     getLeftIndex(i) {
  20.         return i * 2 + 1;
  21.     }
  23.     getRightIndex(i) {
  24.         return i * 2 + 2;
  25.     }
  27.     // O(logn)
  28.     shiftUp(index) {
  29.         if (index === 0) return;
  30.         const parentIndex = this.getParentIndex(index);
  31.         if (this.heap[parentIndex] > this.heap[index]) {
  32.             this.swap(parentIndex, index);
  33.             this.shiftUp(parentIndex);
  34.         }
  35.     }
  37.     // O(logn)
  38.     shiftDown(index) {
  39.         const leftIndex = this.getLeftIndex(index);
  40.         const rightIndex = this.getRightIndex(index);
  41.         if (this.heap[leftIndex] < this.heap[index]) {
  42.             this.swap(leftIndex, index);
  43.             this.shiftDown(leftIndex);
  44.         }
  45.         if (this.heap[rightIndex] < this.heap[index]) {
  46.             this.swap(rightIndex, index);
  47.             this.shiftDown(rightIndex);
  48.         }
  49.     }
  51.     insert(val) {
  52.         this.heap.push(val);
  53.         this.shiftUp(this.heap.length - 1);
  54.     }
  56.     pop() {
  57.         this.heap[0] = this.heap.pop();
  58.         this.shiftDown(0);
  59.     }
  61.     peek() {
  62.         return this.heap[0];
  63.     }
  65.     size() {
  66.         return this.heap.length;
  67.     }
  68. }
  70. const a = new MinHeap();
  71. a.insert(3)
  72. a.insert(2)
  73. a.insert(4)
  74. a.insert(5)
  75. a.insert(1)
  76. console.log(a.heap);// [ 1, 2, 4, 5, 3 ]
  77. a.pop()
  78. console.log(a.heap);// [ 2, 3, 4, 5 ]
  79. console.log(a.peek());// 2
  80. console.log(a.size());// 4

题目

数组中的第K个最大元素

思路：让堆只能存 K 个元素，超过 K 数量的元素都删除，最终只剩下 K 个元素。等堆排序完后，堆顶就是最小的元素，即第 K 个最大的元素。
image.png

  1. class MinHeap {
  2.     constructor() {
  3.         this.heap = [];
  4.     }
  6.     swap(i1, i2) {
  7.         // const tmp = this.heap[i1];
  8.         // this.heap[i1] = this.heap[i2];
  9.         // this.heap[i2] = tmp;
  10.         [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]
  11.     }
  13.     getParentIndex(i) {
  14.         // return Math.floor((i - 1) / 2);
  15.         // 位运算：将二进制向右移一位，也就相当于除 2
  16.         return (i - 1) >> 1;
  17.     }
  19.     getLeftIndex(i) {
  20.         return i * 2 + 1;
  21.     }
  23.     getRightIndex(i) {
  24.         return i * 2 + 2;
  25.     }
  27.     shiftUp(index) {
  28.         if (index === 0) return;
  29.         const parentIndex = this.getParentIndex(index);
  30.         if (this.heap[parentIndex] > this.heap[index]) {
  31.             this.swap(parentIndex, index);
  32.             this.shiftUp(parentIndex);
  33.         }
  34.     }
  36.     shiftDown(index) {
  37.         const leftIndex = this.getLeftIndex(index);
  38.         const rightIndex = this.getRightIndex(index);
  39.         if (this.heap[leftIndex] < this.heap[index]) {
  40.             this.swap(leftIndex, index);
  41.             this.shiftDown(leftIndex);
  42.         }
  43.         if (this.heap[rightIndex] < this.heap[index]) {
  44.             this.swap(rightIndex, index);
  45.             this.shiftDown(rightIndex);
  46.         }
  47.     }
  49.     insert(val) {
  50.         this.heap.push(val);
  51.         this.shiftUp(this.heap.length - 1);
  52.     }
  54.     pop() {
  55.         this.heap[0] = this.heap.pop();
  56.         this.shiftDown(0);
  57.     }
  59.     peek() {
  60.         return this.heap[0];
  61.     }
  63.     size() {
  64.         return this.heap.length;
  65.     }
  66. }
  68. const findKthLargest = function (nums, k) {
  69.     const h = new MinHeap();
  70.     nums.forEach(n => {
  71.         h.insert(n);
  72.         if (h.size() > k) {
  73.             h.pop();
  74.         }
  75.     })
  76.     return h.peek();
  77. }
  78. console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 5));

前 K 个高频元素

解法一

  1. const topKFrequent = function (nums, k) {
  2.     const map = new Map();
  3.     //  forEach 的时间复杂度为 O(n)
  4.     nums.forEach(n => {
  5.         map.set(n, map.has(n) ? map.get(n) + 1 : 1)
  6.     })
  7.     // 数组原生的 sort 方法为  O(nlogn)
  8.     const list = Array.from(map).sort((a, b) => b[1] - a[1]);
  10.     return list.slice(0, k).map(n => n[0]);
  11. };
  12. // 两个时间复杂度取最大值，所以时间复杂度为 O(nlogn)。不满足题目要求。

解法二

  1. class MinHeap {
  2.     constructor() {
  3.         this.heap = [];
  4.     }
  6.     swap(i1, i2) {
  7.         // const tmp = this.heap[i1];
  8.         // this.heap[i1] = this.heap[i2];
  9.         // this.heap[i2] = tmp;
  10.         [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]
  11.     }
  13.     getParentIndex(i) {
  14.         // return Math.floor((i - 1) / 2);
  15.         // 位运算：将二进制向右移一位，也就相当于除 2
  16.         return (i - 1) >> 1;
  17.     }
  19.     getLeftIndex(i) {
  20.         return i * 2 + 1;
  21.     }
  23.     getRightIndex(i) {
  24.         return i * 2 + 2;
  25.     }
  27.     shiftUp(index) {
  28.         if (index === 0) return;
  29.         const parentIndex = this.getParentIndex(index);
  30.         // 注意：这里的逻辑有所改动
  31.         if (this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value) {
  32.             this.swap(parentIndex, index);
  33.             this.shiftUp(parentIndex);
  34.         }
  35.     }
  37.     shiftDown(index) {
  38.         const leftIndex = this.getLeftIndex(index);
  39.         const rightIndex = this.getRightIndex(index);
  40.         if (this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value) {
  41.             this.swap(leftIndex, index);
  42.             this.shiftDown(leftIndex);
  43.         }
  44.         if (this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value) {
  45.             this.swap(rightIndex, index);
  46.             this.shiftDown(rightIndex);
  47.         }
  48.     }
  50.     insert(val) {
  51.         this.heap.push(val);
  52.         this.shiftUp(this.heap.length - 1);
  53.     }
  55.     pop() {
  56.         this.heap[0] = this.heap.pop();
  57.         this.shiftDown(0);
  58.     }
  60.     peek() {
  61.         return this.heap[0];
  62.     }
  64.     size() {
  65.         return this.heap.length;
  66.     }
  67. }
  70. const topKFrequent = function (nums, k) {
  71.     const map = new Map();
  72.     nums.forEach(n => {
  73.         map.set(n, map.has(n) ? map.get(n) + 1 : 1)
  74.     })
  75.     const h = new MinHeap();
  76.     // forEach O(n)
  77.     map.forEach((value, key) => {
  78.         //  O(logk)
  79.         h.insert({value, key})
  80.         if (h.size() > k) {
  81.             //  O(logk)
  82.             h.pop();
  83.         }
  84.     })
  85.     return h.heap.map(a => a.key);
  86. };
  87. // 最终的时间复杂度为  O(nlogk)

合并K个升序链表

image.png

滑动窗口最大值

  1. 使用最大堆实现：堆里只存3个元素，每次移动窗口就是添加一个元素。
  2. 使用优先队列实现：队列的队头永远存放最大的值，每次新进一个值时，都去和队头比较，如果比队头大就删除队列里的所有元素（包括队头），然后再将该元素入队。

参考

百度百科

数据结构脑图
https://naotu.baidu.com/file/0a53d3a5343bd86375f348b2831d3610?token=5ab1de1c90d5f3ec
https://naotu.baidu.com/file/b832f043e2ead159d584cca4efb19703?token=7a6a56eb2630548c