5.1 堆（heap）(解决优先队列)
5.1.1 定义
定义 ：
优先队列（Priority Queue）：特殊的“ 队列”，取出元素的顺序是依照元素的优先权（关键字） 大小，而不是元素进入队列的先后顺序。即可认为：
每个加入队列的值有一定的意义（大小），进入队列没有规定，但是出队列要根据一定的意义（大小）出队列。
5.1.2 存储和特性
我们运用优先队列的
完全二叉树 ：特性：
1.结构性 ：用数组表示的完全二叉树；
2. $\color{有序性** ： 任一结点 的关键字是其子树所有结点的最大值( 或最小值)
- “最大堆(MaxHeap)”,也称”大顶堆”：最大值
- “最小堆 ( MinHeap)”,也称”小顶堆”：最小值
5.1.3 堆抽象数据类型
5.1.3.1插入
5.1.3.2 删除
5.1.4 总结
1.了解堆的定义和结构；
2.会识别最大堆和最小堆，能做出相关习题；
3.编程（插入、删除、建立）。
5.2 哈夫曼树(解决编码)
5.2.1 定义
例：将百分制的考试成绩转换成五分制的成绩？
如何根据结点不同的查找频率构造更有效的搜索树？
带权路径长度 (WPL) ： 设二叉树有n 个叶子结点 ，每个叶子结点带有权值wk ，从根结点到每个叶子结点的长度为lk ，则每个叶子结点的带权路径长度之和就是：
WPL=∑ni=1wklk
哈夫曼树 （最小二叉树）：WPL最小的二叉树。
5.2.2 构造与特点
1.
- 把数据从小到大进行排列（构造最小堆）；
- 每次把 权值最小的两棵 二叉树（节点）合并。
2.
- 没有度为1 的结点；
n 个叶子结点的 哈夫曼树共有2n−1 个结点 ；- 哈夫曼树的任意非叶节点的 左右子树交换 后仍是哈夫曼树 ；
- 对同一组 权值
{w1,w2,……,wn} ，存在 不同构的两棵哈夫曼树。例如：
对一组 权值{1,2,3,3} ，可构成：不同构 的两棵哈夫曼树。
5.2.3 哈夫曼树编码
1.
给定一段字符串，如何 对字符进行编码 ，可以使得该字符串的编码存储空间最少！
例：假设有一段文本，包含
进行不等长编码需注意：
前缀码 (prefix code )：任何字符的编码都不是另一字符编码的前缀。用
二叉树 进行编码（编码代价最小）：
（1 ）左右分支：0 、1 ；
（2 ）字符只在叶结点上。
2.
- 为五个使用频率不同的字符设计哈夫曼编码，下列方案中哪个不可能是哈夫曼编码？
A. 00，100，101，110，111
B. 000，001，01，10，11
C. 0000，0001，001，01，1
D. 000，001，010，011，1**解析：**A
判别是否是前缀码的算法 根据编码规则建立一个编码树，然后对于任何给定的要判断的码，起始结点设为根结点，读到一个0，转到左儿子，读到一个1，转到右儿子，直到读完，这时检查走到的结点是不是叶子结点~因为没有提到是最优编码，所以构成的编码树树不一定是哈夫曼树，该结点不必须由两个儿子。
5.3 集合
集合运算 ： 交、并、补、差，判定 一个元素是否属于某一集合。并查集 ：集合 并、查找 某元素属于什么集合。
- 可以 用 树结构 表示集合；
- 采用数组存储形式。
查找（返回根节点）
并集合（一个根结点的父结点指针设置成另一个根结点 的数组下标）
5.4
#include<stdio.h>
#define MAXH 1001
#define MINH -10001
int H[MAXH],size;
void Create()
{
size = 0;
H[0] = MINH;
/*设置"岗哨"*/
}
void Insert(int X)
{
int i;
for(i=++size;H[i/2]>X;i/=2)
H[i] = H[i/2];
H[i] = X;
}
int main()
{
int count,outCount,x,i,outNumb;
scanf("%d %d",&count,&outCount);
Create();
for(i = 0; i < count; i++)
{
scanf("%d",&x);
Insert(x);
}
for(i = 0; i < outCount ; i++)
{
scanf("%d",&outNumb);
printf("%d",H[outNumb]);
while(outNumb>1)
{
outNumb/=2;
printf(" %d",H[outNumb]);
}
printf("\n");
}
return 0;
}