云昴

【算法2】基础+贪心

| 算法

BST && BBST

从根开始搜索。

BST

所有的左后代都小于父代,右后代都大于父代,才能满足。

Balance Binary Search Tree, 平衡二叉搜索树,能够更好的提高搜索效率。

散列表

这里,我们先讨论一下散列表(哈希表),作为一个数组,可以很快的查找到。哈希冲突,是需要处理的,可以用链进行链接。

散列表

取模一般使用素数,为什么使用素数?(如果对一个合数取模,那么对其某个因数取模,结果可能仍然一致。例如 10 对 8 取模,结果为 2,对 4 取模,结果也为 2。而我们对一个素数取模,由于素数只有 1 和其本身两个因素,即不可能出现上述情形。)

Hashtable are also used in Dictionary and Map.

Huffman Tree 2

回顾之前的Huffman Trees, 如何进行排序?

我们引入优先队列。

Priority Queue

我们同样可以使用Stack+Queue的方式。

Stack+Queue

首先将需要编码的数进行排序,存入Stack中,之后取出2个相加,存入队列中。

a) 比较stack.pop() 和 queue.dequeue(), 取出最小的两个。

b) 将两数相加,存入队列。

直到合并为最后一个。

Minimum Spanning Tree 最小生成树

Prim: cut + cross

cut + cross

Prim算法

  1. 输入:一个加权连通图,其中顶点集合为V,边集合为E;

  2. 初始化:Vnew = {x},其中x为集合V中的任一节点(起始点),Enew = {},为空;

  3. 重复下列操作,直到Vnew = V:

    a. 在集合E中选取权值最小的边,其中u为集合Vnew中的元素,而v不在Vnew集合当中,并且v∈V(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一);

    b. 将v加入集合Vnew中,将边加入集合Enew中;

  4. 输出:使用集合Vnew和Enew来描述所得到的最小生成树。

Prim

矩阵实现的话,效率会低

云昴