Algorithms note

单链表
1)插入：
在p和p->next中插入s
a)s->next = p->next;
b)p->next = s;
2)删除： p->next = p->next->next;

双链表
1)插入
在p和p->next中插入s
a)s-prior = p; b)s-next = p->next; c)p->next-prior = p; d)p-next = s;
2)删除
a)p->prior->next = p->next; b)p->next->prior = p-prior;

逆波兰算法
1）中缀表达式转后缀表达式：从左到右遍历表达式中的数字与符号，如果是数字，就输出到后缀表达式；如果是符号，则比较该符号与栈顶符号的优先级，若该符号是右括号或优先级不高于栈顶符号，则栈顶符号出栈并进入后缀表达式，直到当前符号优先级大于栈顶符号或栈空，然后当前符号进栈。
2）后缀表达式运算： 从左到右遍历表达式，遇到数字就进栈，遇到符号则弹出栈中数字进行运算（后弹－符号－先弹），并将结果压栈。

树
1）结点的层次从根开始，根在第一层
2）树的存储结构：
a.双亲表示法：只知道当前结点的双亲（两个字段：data+parent）
b.孩子表示法：只知道当前结点的孩子（N个字段：data[+how many child]+child1+child2+child3+……）或两种结点（孩子结点：child+next；表头结点：data+firstchild）
c.孩子兄弟表示法：只知道该结点的第一个孩子和右兄弟（三个字段：data+firstchild+rightsib，把树变成二叉树）

二叉树
1)特点：每个结点最多两颗子树，左子树和右子树是有顺序的
2)满二叉树：a.所有分支结点都有左、右子树；b.所有叶子结点都在同一层
3)完全二叉树：a.叶子只能出现在最下面两层；b.最下层的叶子连续集中于左边；c.同样结点的二叉树，完全二叉树深度最小

二叉树的性质
1)在二叉树的第i层，最多有(2的(i－1))次方的结点（根结点是第1层）
2)深度为k的二叉树，最多有((2的k次方)－1)个结点(根结点深度为1，所以需要减1)
3)任意二叉树，叶子结点数为n0，度为2的结点数为n2，则n0 ＝ n2 ＋ 1（证明：总结点数等于度为0，1，2结点数之和：n＝n0+n1+n2；总链接数等于总结点数减一，因为根结点无入度：n－1=n1＋2＊n2，两个公式合并即证）
4)n个结点的完全二叉树的深度为 ((以2为底n的对数向下取整)＋1)
5)n个结点的完全二叉树，任一结点i，如果i>1，则其双亲是i/2向下取整；如果其有子结点，则左孩子是2i，右孩子是2i＋1

哈夫曼树：
1)构建时由下往上，小小成大
2)编码时由上往下，左右分开
3)解码从前向后解析，匹配就OK

最小生成树：
1)Prim算法：从某点开始，每次选该点所在图的紧临最小边。复杂度O(n2次方)，n为点数
2)Kruskal算法：从所有边中，每次选最小的未选中的边。复杂度O(eloge), e为边数

最短路径算法：
1)Dijkstra算法：求两点间最短路径
2)Floyd算法：所有点互相间最短路径

查找
1)顺序查找(O(n))
2)二分查找(Olog(n))
3)多路查找树：其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系
4)2-3树：是这样一颗多路查找树：其中的每一个结点都具有两个孩子（我们称之为2结点）或三个孩子（称之为三结点）。一个二结点包含一个元素和两个孩子（或没有孩子），左孩子小于该结点值，该结点值小于右孩子。一个三结点包含一小一大两个元素和三个孩子（或没有孩子），左孩子小于小值，右孩子大于大值，中间孩子介于两者之间。
5)二叉排序树：又称二叉查找树。它或者是一颗空树，或者满足如下性质：a.若它的左子树不空，则左子树上所有的结点值都小于根结点的值；b.若它的右子树不空，则右子树上左右的结点值都大于根结点的值；c.它的左右子树也分别为二叉排序树
6)平衡二叉树（AVL）：也是二叉排序树，但是任意结点左右子树的高度差不大于1
注：引入2-3树是为了保证所有的查找都能在lgN次比较内结束，也是为了保证查找树的平衡性。

B树
B树是一种平衡的多路查找树，2-3树是B树的特例。结点最大的孩子数目称为B树的阶，因此，2-3树是3阶B树。一个m阶B树具有如下属性
1)如果根结点不是叶结点，则其至少有两颗子树
2)每一个非根的分支结点都有k－1个元素和k个孩子，每一个叶子结点n都有k－1个元素。其中k大于m的一半向上取整，且小于m。
3)所有叶子结点都位于同一层
4)所有分支结点规则与2-3树相同，且每一个分支结点有一个值n用来表示该结点关键字的个数
5)B+树其实已经不是严格的树了，它在B树的基础上把同一层的结点都链接起来。因此它很适合范围的查找，比如18-22岁的人的查找，先从上往下找到18，然后从左往右找到22.
6)红黑树：红黑二叉查找树背后的基本思想是用标准的二叉查找树和一些额外的信息来表示2-3树。

排序
1)堆是具有下列性质的完全二叉树（少一部分右边叶子结点的满二叉树）：每个结点的值都大于等于左右孩子结点的值（大顶堆）；或者小于等于（小顶堆）
2)堆和二叉排序树的差别：堆是完全二叉树，且堆是结点大于左右子树，而二叉排序树是大于左边，小于右边

MySQL Hash索引和B-Tree索引的区别
1）MySQL Hash索引仅仅能满足”=”,”IN”和”<=>”查询，不能使用范围查询
2）MySQL Hash索引无法被用来避免数据的排序操作。
3）MySQL Hash索引不能利用部分索引键查询
4）MySQL Hash索引在任何时候都不能避免表扫描
5）MySQL Hash索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高
MySQL哈希索引
B tree 索引
B tree 索引

HashMap的实现

Top K
参考：http://blog.csdn.net/jj8582/article/details/6890521

大数相除
不用BigInteger