数据结构.png
堆Heap
定义
优先队列（Priority Queue）： 取出元素的大小是根据元素的优先权（关键字）大小
最大堆（MaxHeap）：大顶堆：最大值 - 每个结点的元素值不小于其左右子树的元素值
最小堆（MinHeap）：小顶堆：最小值
应用例子: CPU调度
存储：完全二叉树
结构性：用数组表示的完全二叉树
基本操作
i. 判断堆满：size == maxSize
ii. 插入：
放在数组最后，如果不满足有序性，则交换父节点（i/2）与当前数(i )
iii. 删除
取出根节点元素，把最后一个元素放至根节点
依次比较和交换，直到满足有序性
哈夫曼树Huffman Tree
定义
a. 最优二叉树：（带权路径长度）WPL最小的二叉树，
WPL： sum（叶子结点的权重W_k * 从根节点到叶子结点从长度L_k ）
构造
i. 每次把权值最小的两颗二叉树合并，合并后的权值为该权值的和
ii. 利用MinHeap
iii. O(log n）
特点
i. 没有度为1的结点 -> 每次构造都是两个结点
ii. n个叶结点的哈夫曼树共有2n-1个结点
iii. 哈夫曼树左右树交换依然是哈夫曼树
iv. 相同的权值，可能产生不同的哈夫曼树（不唯一），但WPL是一样的
应用：哈夫曼编码
a. 对字符进行编码，使得存储空间最少： 频率高的字符，编码长度短
b. 左右分支：0,1
c. 字符只在叶结点上 -》 可避免二义性
图
定义：多对多关系
基本概念：顶点V(Vertex)、边（Edge）
边是顶点对：无向边(v, w)， 有向边<v, w>
无向图、有向图、网络（带权的图）
存储方式：
a. 邻接矩阵：
- 对角线元素为0
- 无向图是对称的 -》 减少一半的空间 ： （i * （i+1）/2 +j）
- 方便计算度：扫描行或者列
- 稀疏图
b.邻接表：链表的集合
- 为每一个结点创建一个链表，表示与它相连的结点
- 每条边被存了两次
- 度：对无向图来说容易计算；对于有向图来说，只能计算出度，入度需要构造逆邻接表
c. 十字链表
图的遍历
a. BFS：利用队列queue实现
b. DFS：利用栈stack实现
最短路径问题：求两个不同顶点之间的所有路径 中，边的权值之和最小的那一条路径
- NOTATION
a. 第一个顶点为源点（Source）
b. 最后一点顶点为终点（Destination） - 问题分类：
i. 单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
ii. 多源：可以用单源的方法把所有的顶点都跑一遍 - 具体步骤
i. 单源最短路径： 无权图：类似BFS - 时间复杂度；有权图：Dijkstra算法 - 时间复杂度
ii. 多源最短路径：Floyd算法 - 用于稠密图 - 时间复杂度：
（注：
利用邻接矩阵储存图
初始为：
a. 无边：无穷大
b. 有边：权重
c. 对角元：0
如果需要输出路径，重新定义二维数组Path[i][j]）
最小生成树（Minimum Spanning Tree）：最小连通子图
定义
i. 树：连通、无回路、v个顶点一定有v-1条边
ii. 生成树：包含全部顶点、v-1条边都在图里、任加一条边都一定会构成回路
iii. 边的权重和最小
贪心算法：每一个步都是最好的
约束条件
i. 只能用图里的边
ii. 只能刚好用v-1条边
iii. 不能有回路
Prim算法 - 小棵树长大
i. 每次比较顶点与已选择的树的最小距离
Kruskal算法 - 将森林合并成树
i. 选择权重最小的边知道v-1条边，保证无回路
ii. 最小堆、并查集
拓扑排序
a. AOV（Activity On Vertex）网络
b. 有向无环图（Directed Acyclic Graph, DAG）
c. 关键路径
- AOE（Activity On Edge）网络：边表示活动，顶点表示时间
- 由绝不允许延误的活动组成的路径
- Earliest Time, Latest Time
- 机动时间
网友评论