完全二叉树有个非常高效的存储方法，就是数组，一般的树都要用链表去存储。
对于heap sort的输入数组，如A[16,14,10,8,7,9,3,2,4,1]，要进行堆排序，首先要建堆，建堆可以分为两步：
将输入数组抽象成完全二叉树 建堆BUILD-MAX-HEAP 开始建堆，
先来学习一个重要的堆操作MAX-HEAPIFY
这个函数就是对数组A中的第i个节点进行heapify操作
其实比较简单，1～7就是比较找出，i节点和左右子节点中，哪个最大
8～10，如果最大的不是i，那就把最大节点的和i节点交换，然后递归对从最大节点位置开始继续进行heapify
显而易见，对于n个节点的完全二叉树，高为lgn，对每个节点的heapify操作是常数级的，所以这个操作的时间复杂度就是lgn 6.3 建堆
那么有了heapify操作，建堆的算法很简单的，
说白了，就是对i从length[A]/2到1的节点进行heapify操作。所以这个操作的时间复杂度上限咋一看应该是nlgn，其实比这个小的多，约等于2n，就是说建堆的时间复杂度是O(n)，能够在线性时间内完成，这个是很高效的。
所以我们只需要对所有非叶节点进行heapify操作就ok了 6.4 堆排序算法
折腾半天堆建好了，怎么堆排序了，光从堆是得不到一个有序序列的。
原理很简单，从堆我们只能知道最大的那个，那么就把最大的那个去掉，然后heapify找到第二大的，依次下去。
实现也很巧妙，没有用到额外的存储空间，把堆顶放到堆尾，然后堆size-1 这个算法的时间复杂度也是nlgn。
堆排序算法最重要的三步就是：保持堆的性质，建堆，堆排序算法
5. 哈希。哈希函数的有哪些种？余数的取法？ 处理冲突的方法？ 闭散列方法有哪些？ 哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里。
构造哈希函数的方法很多，这里只介绍一些常用的，计算简便的方法。 1.平方取中法
算出关键字值的平方，再取其中若干位作为哈希函数值 ( 散列地址 ) 。 2.除留余数法
这种方法是用模运算 (%) 得到的。设给出的关键字值为 K ，存储区单元数为 m ，则用一个小于 m 的质数 P 去除 K ，得到的余数为 R ，即： R ＝ K % P 。如果 R 落在存储区地址范围内，则 R 就取为哈希函数值 ( 散列地址 ) ；否则，再用一个线性数求出哈希函数值。 3.数字分析法
对各个关键字内部代码的各个码位进行分析。假设有 n 个 d 位的关键字，使用 s 个不同的符号 ( 如，对于十进制数，每一位可能出现的符号有 10 个，即 0 、 1 、 2 、…、 9) ，这 s 个不同的符号在各位上出现的频率不一定相同，它们可能在某些位上分布比较均匀，即每一个符号出现的次数都接近 n/s 次；而在另一些位上分布不均匀。这时，选取其中分布比较均匀的某些位作为哈希函数值 ( 散列地址 ) ，所选取的位数应视存储区地址范围而定，这就是数字分析法。注意： 这种方法适合于关键字值中各位字符分布为已知的情况。
构造哈希函数除了上面介绍的几种常用方法外，还有截段法，即截取关键字中的某一段数码作为哈希函数；分段迭加法，即把关键字的机内代码分成几段，再进行迭加 ( 可以是算术加，也可以是按位加 ) 得到哈希函数值。解决哈希（HASH）冲突的主要方法
a) 开放地址法
这个方法的基本思想是：当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。这个过程可用下式描述：
H i ( key ) = ( H ( key )+ d i ) mod m ( i = 1,2,…… ， k ( k ≤ m – 1))
其中： H ( key ) 为关键字 key 的直接哈希地址， m 为哈希表的长度， di 为每次再探测时的地址增量。
采用这种方法时，首先计算出元素的直接哈希地址 H ( key ) ，如果该存储单元已被其他元素占用，则继续查看地址为 H ( key ) + d 2 的存储单元，如此重复直至找到某个存储单元为空时，将关键字为 key 的数据元素存放到该单元。 增量 d 可以有不同的取法，并根据其取法有不同的称呼： （ 1 ） d i ＝ 1 ， 2 ， 3 ， …… 线性探测再散列；
（ 2 ） d i ＝ 1^2 ，－ 1^2 ， 2^2 ，－ 2^2 ， k^2， -k^2…… 二次探测再散列； （ 3 ） d i ＝ 伪随机序列 伪随机再散列； b)再哈希法
当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点：计算时间增加。 c)链地址法
将所有关键字为同义词的记录存储在同一线性链表中。如下：
因此这种方法，可以近似的认为是筒子里面套筒子
与开放定址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间； ④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结 点的空间置为空，
否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在 用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
（3）拉链法的缺点
拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
冲突解决策略/闭散列方法
闭散列方法把所有记录直接存储在散列表中。每个记录关键码key有一个由散列函数计算出来的基位置，即h(key)。如果要插入一个关键码，而另一个记录已经占据了R的基位置(发生碰撞)，那么就把R存储在表中的其它地址内，由冲突解决策略确定是哪个地址。
闭散列表解决冲突的基本思想是：当冲突发生时，使用某种方法为关键码K生成一个散列地址序列d0，d1，d2，... di ，...dm-1。其中d0=h（K）称为K的基地址地置( home position )；所有di(0< i< m)是后继散列地址。当插入K时，若基地址上的结点已被别的数据元素占用，则按上述地址序列依次探查，将找到的第一个开放的空闲位置di作为K的存储位置；若所有后继散列地址都不空闲，说明该闭散列表已满，报告溢出。相应地，检索K时，将按同值的后继地址序列依次查找，检索成功时返回该位置di ；如果沿着探查序列检索时，遇到了开放的空闲地址，则说明表中没有待查的关键码。删除K时，也按同值的后继地址序列依次查找，查找到某个位置di具有该K值，则删除该位置di上的数据元素（删除操作实际上只是对该结点加以删除标记）；如果遇到了开放的空闲地址，则说明表中没有待删除的关键码。因此，对于闭散列表来说，构造后继散列地址序列的方法，也就是处理冲突的方法。
形成探查的方法不同，所得到的解决冲突的方法也不同。下面是几种常见的构造方法。 1、线性探查法
将散列表看成是一个环形表，若在基地址d（即h(K)=d）发生冲突，则依次探查下述地址单元：d+1，d+2，......，M-1，0，1，......，d-1直到找到一个空闲地址或查找到关键码为key的结点为止。当然，若沿着该探查序列检索一遍之后，又回到了地址d，则无论是做插入操作还是做检索操作，都意味着失败。 用于简单线性探查的探查函数是： p(K，i) = i
例9.7 已知一组关键码为（26，36，41，38，44，15，68，12，06，51，25），散列表长度M= 15，用线性探查法解决冲突构造这组关键码的散列表。
因为n=11，利用除余法构造散列函数，选取小于Ｍ的最大质数P=13，则散列函数为：h(key) = key。按顺序插入各个结点： 26: h(26) = 0，36: h(36) = 10， 41: h(41) = 2，38: h(38) = 12， 44: h(44) = 5。
插入15时，其散列地址为2，由于2已被关键码为41的元素占用，故需进行探查。按顺序探查法，显然3为开放的空闲地址，故可将其放在3单元。类似地，68和12可分别放在4和13单元中，下图显示了插入15和68时的过程。
2、二次探查法
二次探查法的基本思想是：生成的后继散列地址不是连续的，而是跳跃式的，以便为后续数据元素留下
空间从而减少聚集。二次探查法的探查序列依次为：12，-12，22 ，-22，...等，也就是说，发生冲突时，将同义词来回散列在第一个地址的两端。求下一个开放地址的公式为：
3、随机探查法
理想的探查函数应当在探查序列中随机地从未访问过的槽中选择下一个位置，即探查序列应当是散列表位置的一个随机排列。但是，我们实际上不能随机地从探查序列中选择一个位置，因为在检索关键码的时候不能建立起同样的探查序列。然而，我们可以做一些类似于伪随机探查( pseudo-random probing )的事情。在伪随机探查中，探查序列中的第i个槽是(h(K) + ri) mod M，其中ri是1到M - 1之间数的―随机‖数序列。所有插入和检索都使用相同的―随机‖数。探查函数将是 p(K，i) = perm[i - 1]， 这里perm是一个长度为M - 1的数组，它包含值从1到M – 1的随机序列。 4、双散列探查法
伪随机探查和二次探查都能消除基本聚集——即基地址不同的关键码，其探查序列的某些段重叠在一起——的问题。然而，如果两个关键码散列到同一个基地址，那么采用这两种方法还是得到同样的探查序列，仍然会产生聚集。这是因为伪随机探查和二次探查产生的探查序列只是基地址的函数，而不是原来关键码值的函数。这个问题称为二级聚集( secondary clustering )。
为了避免二级聚集，我们需要使得探查序列是原来关键码值的函数，而不是基位置的函数。双散列探查法利用第二个散列函数作为常数，每次跳过常数项，做线性探查。
6. 二叉搜索树的搜索、插入、删除。时间复杂度。
二叉查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树：
1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3. 它的左、右子树也分别为二叉排序树。
二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，期望O(logn),最坏O(n)(数列有序,树退化成线性表).