文章列表
邻接表(adjacency lists)是表示图的标准方法。
如果是稠密图，可以使用邻接矩阵(adjacency matrix)。
BFS(Breadth First Search)，广度优先搜索
DFS(Depth First Search)，深度优先搜索
Topological sort，拓扑排序
适用条件：有向无圈图
DFS方法：将每 ...
斐波那契堆的结构较二项堆更松散，关键思想在于尽量延迟对堆的维护。
A Fibonacci heap is a collection of rooted trees that are min-heap ordered.
根节点不需要顺序，用一个H.min指向最小的
插入一个新节点：就在表数组里插，O(1)，需要调整H.min的值就行。
合并两个堆：也在表数组里插，O(1)，需要调整H.min的值就行。
查询最小的：H.min指向的，O(1)
删除最小的：
1. 先把子树插入到表数组里，然后删除最小的。
2. 用个数组记录度数，然后不停的合并度数相同的树。
为什么取这个名字呢？维基有解释
T ...
Disjoint Set，不相交集，也叫并查集
Union/Find算法：
Find：它返回包含给定元素的集合。
Union：合并两个集合。
用数组来模拟树。
初始化时，数组元素为0。正数的表示父亲是谁，如图：
Union优化：每个根的数组元素包含它的树的高度的负值，按树的高度合并，这样任何节点的深度均不会超过 logN。
第一个数组图是按大小合并，第二个数组图是按高度合并。
按树高度合并代码
typedef int DisjSet[128];
typedef int SetType;
typedef int ElementType;
void SetUnion(DisjSe ...
前面堆排序已经描述了二叉堆的基本操作，插入(O(logn))、删除(O(logn))和查询最大最小值(O(1))，但是两个二叉堆合并时却很不方便，一个一个调用插入方法完成合并需要O(n)。
Binomial Queue(二项队列)：一个链表数组，每个元素指向一棵二项树，数组元素按二项树大小顺序排列。
Binomial Tree(二项树) 是什么 图解
合并两个二项队列 图解
二项队列的插入：就是与一个单节点的堆合并。
查询最大最小：遍历链表数组一遍。
删除最小：将被删除节点的子树变为一个新的二项队列，再与原二项队列合并。
数据结构表示
typedef int ElementType ...
A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK.
红黑树性质：
1. The root is black.
2. If a node is red, then both its children are black.
3. For each node, all simple paths from the node to descendant leaves contain the same num ...
Binary Search Tree
由于经常的插入删除操作会变得越来越不平衡，导致运行效率低下，但删除操作还是蛮漂亮的。
本代码来自《算法导论》，也可以用递归做，但肯定没有迭代效率高。
typedef int ElementType;
typedef struct TreeNode
{
ElementType key;
struct TreeNode *parent;
struct TreeNode *left;
struct TreeNode *right;
} Node, *BST;
// T:root, z:指向要插入节点的指针
void Insert( ...
散列用来以常数时间实现 Insert、Find 和 Delete 操作。
With direct addressing, an element with key k is stored in slot k.(相当于数组)
With hashing, this element is stored in slot h(k); that is, we use a hash function h to compute the slot from the key k.
h(k) 的范围远小于 k，所以必定会产生冲突(Collision)。
哈希函数表大小一般选择素数，可以使得均匀分布，缓解冲突。(为什 ...
中缀表达式：a+b*c+(d*e+f)/g
这是人类擅长的表达式，可是计算机却很为难。
后缀表达式：abc*+de*f+g/+
读到运算数就压栈，读到运算符弹出两个运算数计算，计算结果再压栈，反复...
计算机就很容易计算表达式了。
问题：中缀表达式如何转换成后缀表达式？
1. 读到运算数时，直接输出。
2. 读到“(”时，压栈。
3. 读到“+ - * /”时，弹出栈元素直到优先级更低的元素为止，该符号压栈。(如栈有“+*”，读到“+”，弹出“*+”，再“+”压栈)
4. 读到“)”时，出栈直到“(”
5. 最后全部出栈。
如果把表达式建成一个二叉树，叶子节点为运算数，其他节点为运算符， ...
《算法导论》第三版讲分治时引用了一个很好的例子，股票的涨幅。
而其本质是与《数据结构与算法分析》的开篇一样的，最大子序列和问题。
问题描述：已知每天股票的价格，选择一个买入点和一个抛出点，使得获取利润最大。
问题转换：一个整数序列 A[N](可能有负)，求 A[i] 加到 A[j] 的最大值(0 <= i <= j < N)。如果所有整数均为负数，那么最大子序列和为0。
数组A表示的就是今天股票与昨天的差价。
一、首先会想到，可以用两个循环搞定，O(n^2)。
二、分治，O(nlogn)，copy一下
int maxSubsequenceSum(int A[], int ...
排序算法不仅要考虑效率，还要注意一个易被忽略的因素：稳定性(stable)。
Any comparison sort algorithm requires (nlogn) comparisons in the worst case.(decision tree)
一、插入排序(Insertion Sort)，《算法导论》里那张摸牌的图解释的很形象。稳定的，时间复杂度为 O(n^2)，而其他相同复杂度的排序算法几乎不用考虑。
二、希尔排序(Shell Sort)，插入排序的增强版，但不是稳定的。需要注意gap的选择。
void shell_sort(int A[], int n)
{
...