数据结构与算法 - 高级数据结构
- 1. 优先队列 Priority Queue
-
- 特点
-
-
- 保证每次取出的元素都是队列中优先级别最高的
- 优先级别可以自定义。如：数值越大/小，优先级越高
-
-
- 适用于
-
-
- 从一堆杂乱无章的数据当中按照一定的顺序，逐步筛选出部分乃至全部数据
- 前 K 问题
-
-
- 练习
-
-
- 任意一个数组，找出前 K 大的数
-
-
- 实现
-
-
- 本质：是一个二叉堆结构（数组）
- 二叉堆：利用一个数组结构来实现完全二叉树
- 性质
-
-
-
-
- 1. 数组里的第一个元素 array[0] 拥有最高的优先级别
- 2. 给定一个下标 i，那么对于元素 array[i] 而言
-
-
-
-
-
-
- 它的父节点对应的元素下标是 (i-1)/2
- 它的左孩子对应的元素下标是 2xi + 1
- 它的右孩子对应的元素下标是 2xi + 2
-
-
-
-
-
-
- 3. 数组里每个元素的优先级别都要高于它两个孩子的优先级别
-
-
-
- 基本操作
-
-
- 1. 向上筛选 (sift up / bubble up) - 加入 O(logk)
-
-
-
-
- 当有新的数据加入到优先队列中，新的数据首先被放置在二叉树的底部
- 不断进行向上筛选的操作，即如何发现该数据的优先级别比父节点高，那就和父节点交换，再接着往上进行比较，直到无法 再继续交换为止
-
-
-
-
- 2. 向下筛选 (sift down / bubble down) - 取出 O(logk)
-
-
-
-
- 当堆顶元素被取出时，要更新堆顶的元素作为下一次按照优先级顺序被取出的对象，需要将堆底部的元素放置到堆顶，然后不断地对它执行向下筛选
- 将该元素和它的两个孩子节点对比优先级，如果优先级最高的是其中一个孩子，就将该元素和那个孩子进行交换，然后反复，直到无法继续交换为止
-
-
-
- 练习
-
-
- LC347：给定一个非空的整数数组，返回其中出现频率前 k 高的元素
-
- 2. 图 Graph
-
- 必会知识点
-
-
- 图的存储和表达方式：邻接矩阵 Adjacency Matrix、邻接链表 Adjacency List
- 图的遍历：深度优先、广度优先
- 二部图的检测 Bipartite、树的检测、环的检测：有向/无向图
- 拓扑排序
- 联合 - 查找算法 Union-Find
- 最短路径：Dijkstra、Bellman-Ford
-
-
- 适用于
-
-
- 涉及大数据问题；社交网络；地图查找路径，最短路径
-
-
- 练习
-
-
- LC785：给定一个无向图 graph，当这个图为二部图时 返回 true
-
-
-
-
- 二部图：如果能将一个图的节点集合分割成两个独立的子集 A 和 B，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，成为二部图
- 即：图里所有的边，一头连着 A 集合的顶点，一头连着 B 集合的顶点
-
-
- 3. 前缀树 Trie
-
- 适用于
-
-
- 字典查找，也被成为 字典树
- 网站上的搜索框，会罗列出以搜索文字作为开头的相关搜索信息
- 汉字拼音输入法的联想输出功能
-
-
- 练习
-
-
- LC212：给定一个二维网格和一个字典中的单词列表，找出所有同时在二维网格和字典中出现的单词
-
- 4. 线段树 Segment Tree【没看懂】
-
- 定义
-
-
- 一种按照二叉树的形式存储数据的结构，每个节点保持的都是数组里某一段的总和
- 例：数组是 [1，3，5，7，9，11]，那么它的线段树如下
-
-
-
- 叶子节点为每个元素的数值，根节点是两个子节点的和
-
-
- 适用于
-
-
- 数据很多，且需要频繁 更新 并 求和 的操作
- 假设有一个数组 array[0 ... n-1]，里面有 n 个元素，现在要经常对这个数组做两件事
-
-
-
-
- 1. 更新数组元素的数值
- 2. 求数组任意一段区间里元素的总和（或平均值）
-
-
-
- 练习
-
-
- LC315：给定一个整数数组，按要求返回一个新数组 counts，使得数组 counts 有该性质——counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量
-
-
-
-
- 示例
-
-
-
-
-
-
- 输入 [5, 2, 6, 1]
- 输出 [2, 1, 1, 0]
-
-
-
-
-
-
- 解释
-
-
-
-
-
-
- 5 的右侧有 2 个更小的元素（2 和 1）
- 2 的右侧仅有 1 个更小的元素（1）
- 6 的右侧有 1 个更小的元素（1）
- 1 的右侧有 0 个更小的元素
-
-
-
- 5. 树状数组 Fenwick Tree/Binary Indexed Tree
-
- 特点-基本特征
-
-
- 1. 它是利用数组来表示多叉树的结构，在这一点上和优先队列有些类似，只不过，优先队列是用数组来表示完全二叉树，而树状数组是多叉树
- 2. 树状数组的第一个元素是空节点
- 3. 如果节点 tree[y] 是 tree[x] 的父节点，那么满足条件 y=x-(x & (-x) )
-
-
- 适用于
-
-
- 数据很多，且需要频繁 更新 并 求前 k 总和 的操作
- 假设有一个数组 array[0 ... n-1]，里面有 n 个元素，现在要经常对这个数组做两件事
-
-
-
-
- 1. 更新数组元素的数值
- 2. 求数组前 k 个元素的总和（或平均值）
-
-
-
- 练习
-
-
- LC308：求一个动态变化的二维矩阵里，任意子矩阵里的数的总和
-