stack 栈
先进后出
队列
queue 单端队列
push 相当于push_back
pop 相当于pop_front
deque 双端队列
push_front, pop_front
push_back, pop_back
priority_queue<DateStruct>
实现方式：最大堆
struct DateStruct {
int val;
bool operator < (const DataStruct cmp) const {
// 顺序排序
return val > cmp.val;
}
}
斐波那契堆
实现平均时长为O（1）的插入和删除操作
add()
min_pop()
将最小节点推出后，将其子树与现有子树进行合并
相同维度的树合并
merge()
链表
单向链表
反转、k个一组交换位置
双向链表
相比单向链表优点是可以双向遍历、同时方便增删
循环链表
解决报数问题、约瑟夫环
图
接邻矩阵
node[i]存放节点信息
edge[i][j]存放边信息
接邻表
相比接邻矩阵更加节省空间
求解关键路径
最小生成树
- prim算法
时间复杂度O(nlogn) - 克鲁斯卡算法
时间复杂度O(eloge)
最短路径算法
单源最短路径算法：Dijkstra算法：
执行n次：寻找离出发点最近的节点，计算路经这个节点到达其他节点的距离，更新其他节点
时间复杂度
多源最短路径算法：Floyd-Warshall算法
遍历所有中间节点，计算两两节点途径中间节点的最短路径。
单源有负权回路：Bellman-Ford算法
树
二叉搜索树
平衡二叉树
2-3-4树
红黑树
从2-3-4树如何演化成红黑树的？
2节点 --> 黑节点
3节点-->上黑下红
4节点-->中黑左右红
裂变-->原有4节点的红黑反色，新增节点为红色节点
5大特性代表的原理是啥：
性质1：根节点是黑色。（2-3-4树的根节点都是黑色节点在上）
性质2：每个节点要么是黑色，要么是红色。 （废话）
性质3：每个叶子节点（NIL）是黑色。 （为了保证红黑树特性增加）
性质4：每个红色节点的两个子节点一定都是黑色。 不能有两个红色节点相连。 （2-3-4树中的3、4节点才会有红色节点，红色节点上方必有黑色节点）
性质5：任意一节点到每个叶子节点的路径都包含数量相同的黑结点。（2-3-4树是严格层级相等的树，每个层级对应一个红黑树中的黑色节点）
代码操作拆解：
左旋、右旋
染色
增、删
查找位置
nothing else~
