导言：
我们在以前的学习中知道了堆栈，和队列，在系统处理上这两种数据结构的确是很高效的，但是在系统的任务调度上就是很高效了，我们cpu处理任务是有优先级的，要是按照队列和栈的思想都是线性执行，可能发生的情况就是输出一个字符比系统掉电请求处理的优先级高，可能输出一个字符先来，所以在任务调度上线性结构就会有明显的劣势，现在我们要学习的堆能否解决这一问题呢？
一.堆的相关定义和操作
什么是堆？
堆其实就是一种特殊的队列，即优先队列
它是按照已有元素的优先级来排列的，它的优先级高的在堆顶，优先级低的在堆低
堆的实现
堆的实现有很多
队列实现：本身堆就是一个优先级队列，使用队列实现可以，但是新增的元素，增删改需要大量的移动，所以不建议使用
二叉树实现：实际上我们最常用的实现就是二叉树实现，优先级高的在父结点，优先级低的在子结点，增删改比线性结构要方便的多
二叉树实现堆：
二叉树实现堆一定要满足，树是完全二叉树
如上图：
完全二叉树在除了最后一层可以有空缺外，其它层都是满的，而且最后一层的数据应该是在集中在左子树，只要同一层的左子树没有满，右子树可以没有数据
构造堆的二叉树可以不是查找二叉树，毕竟那要求太严苛了，一旦有了连续的数据肯定会导致二叉树成为线性结构，所以构造堆的时候不偏向查找二叉树，而是偏向完全二叉树
构造堆的完全二叉树应该要保证，树的父结点是大于子结点的，子结点可以无序，左节点和右结点谁大无所谓
如上图：
这就是构建堆中的两种基本类型的堆，大顶堆和小顶堆
大顶堆：完全二叉树的情况下，父结点的值 “大于” 任一子结点
小顶堆：完全二叉树的情况下，父结点的值 “ 小于” 任一子结点
堆的有序性：
不管是大顶堆还是小顶堆，都应该满足从根结点出发，到任一子结点都是有序的（可能是递增序列，可能是递减序列）
堆的操作
选用链表的形式来实现二叉树：
typedef int ElementType; typedef struct HeapStruct* MaxHeap; struct HeapStruct { ElementType* Elements; //存储堆中的元素 int Size; //堆中当前的元素个数 int Capacity; //堆的最大容量 };
上面就是树结点的结构：
通过 Elements 来存储元素的值
通过 Size 来记录当前的位置，以及 + 1 后下一个元素的位置
通过 Capacity 来表示堆的最大容量，用来限制堆是否可以存储，且它的默认位置数组下标的 0 号空间
堆的插入操作（大顶堆）：
建堆前我们需要有一些准备工作，比如先把数组的0号元素作为岗哨，申请堆空间的大小，初始化堆的一些信息等等
MaxHeap Create(int Maxsize) { MaxHeap H = malloc(sizeof(struct HeapStruct)); H->Elements=malloc((Maxsize+1)*sizeof(ElementType)); H->Size = 0; H->Capacity = Maxsize; H->Elements[0] = MaxData; return H; }
上面的代码就是需要我们初始化堆的一些特性，比如存储数据的大小等等
堆的插入特点：
- 先按照完全二叉树的结构插入新数据
- 当父结点的值小于新插入子结点时和父结点互换
- 每次互换都要向上继续检查，有可能新数据是最大的子结点
void Insert(MaxHeap H, ElementType number) { int i; if (H->Size == H->Capacity) { printf("堆已经满了！"); return; } i = ++H->Size; for (; H->Elements[i / 2] < number; i /= 2) { H->Elements[i] = H->Elements[i / 2]; } H->Elements[i] = number; }
上面就是堆插入的代码：
它首先判断了堆内数组还有没有空闲的空间，如果没有了就不能插入了，反之便可以
然后就是通过循环，如果当前结点比父结点小，或者等于父结点，那么就不需要变动
如果比父结点大，那么就需要经过内循环的移动覆盖掉父结点，就是等于把父结点的元素移动到插入的子结点上，
这里需要注意的是 循环内执行的代码变量 i 和 最后把新元素赋值到结点内的 i 它们的值不是最开始的 H->Size
堆的删除操作（大顶堆）：
堆的删除操作可以分为两步：
第一步，把要删除的元素和最后一个元素位置对调，可以采用最后一个位置直接覆盖掉要删除位置的元素，然后再断链最后一个元素
第二步，从被覆盖的位置开始，维护堆，即如果被换上来的元素小于子结点，那么就把子结点大的交换上来，继续递归知道，此结点大于子结点，或它自己是叶结点
ElementType DeleteMax(MaxHeap H) { int parent, child; ElementType MaxItem, temp; if (H->Size == 0) { printf("堆空，无需操作"); return; } MaxItem = H->Elements[1]; //拿到最大结点 temp = H->Elements[H->Size--]; //分号作用域内，先赋值后自减 for (parent = 1;parent * 2 <=H->Size; parent = child) { child = parent * 2; //左儿子的计算方法 if ((child != H->Size) && (H->Elements[child] < H->Elements[child + 1])) // 第一个条件判定了，有没有右儿子，第二个条件为了找到最大的儿子 child++; if (temp >= H->Elements[child]) //要被交换的元素大于最大的儿子，符合大顶堆 break; else //最大儿子比要被交换的元素大，把最大儿子弄上来当父结点 H->Elements[parent] = H->Elements[child]; } //循环结束表示找到了要被交换元素的位置 H->Elements[parent] = temp; return MaxItem; }
上面是删除堆元素的实现：
由于删除操作都是把优先级高的删除，所以堆删除有个很明显的删除特点，就是每次删除必是删除堆顶元素
删除操作就是和最后一个元素交换，然后断链，维护
这里我们重点来看一下堆的维护
维护有三种情况：
- 需要维护的结点本身就有两个子结点，把最大的子结点交换上来做父结点，自己去做子结点，此时需要循环此操作，又要当下一层的父结点，直到无子结点，或者自己就是最大的子结点
- 需要维护的结点本身只有一个子结点，比较这两个结点，如果子结点更大，那么就交换做父子结点，由于完全二叉树的特性，这种情况下肯定是最后一层才有的，所以交换完成就可以退出了
- 需要维护的结点本身没有子结点，这种情况就不用管它，直接退出
堆的创建操作（大顶堆）：
创建堆的方式一共有两种：
方法一：从建堆开始，一个一个的插入元素，然后逐个的维护已构建好了的堆，它的最大创建代价是 O(N log N)，具体的操作可以参考我前面写的随笔：十大基础排序算法中的堆排序
方法二：在线性条件下，来构建大顶堆，第一步先让序列构建成完全二叉树，第二步调整结点位置，使其满足大顶堆的性质
如上图：
使用这种方式构建堆，它是从最后一个小堆开始维护的，，然后每一层的小堆维护完成以后，就会去上一层，这样一层一层的维护
它的代码描述和上面的删除代码描述很像，可以去仿一下
二.哈夫曼树（应用型）
哈夫曼树是一种树的应用型开发，它是最多使用于编码问题，解决最多使用次数的编码在前面，最少使用的编码在后面
什么是哈夫曼树？
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
如上图：
我们的两种编码方式，第一种是顺序编码，即按字母的先后顺序进行编码的结果，它的平均查找速率是 47
而第二种使用权值来进行编码的结果是 40，明显在相同的树结构下，第二种方式是更高的，也比较符合日常的需求
第二种就是哈夫曼树，也叫最优二叉树：WPL的值最小
WPL：带权路径长度
哈夫曼树的构造
如上图：
哈夫曼树的构造特点是，每次构造都需要从带权序列中拿取两个最小元素作为子结点建堆，它们的父结点是两子结点的权值
父节点会被放回带权序列，继续比较后拿取两个最小的元素作为子结点建堆，然后重复以上操作
哈夫曼树应用编码
我们先来看看一个简单的编码：
我们有a，b，c，d四个字母，我们尽量少的使用二进制数字进行编码，可以怎么做呢？
a：0
b：1
c：10
d：01
我们使用的数字可能是最少的，但是编码能不能使用呢？给定一个序列 1011，它代表那些字母？
是 babb 还是 cbb 还是 bdb ，我们会很明显的发现这一串编码是有二义性的，这样的编码可能满足最少二进制数，但是不能使用
我们接下来要使用的是哈夫曼树来实现编码：
上面的编码不能使用是因为很多编码都不是前缀码。
前缀码：任何字符的编码都不是另一字符编码的前缀 （可以无二义解码）
哈夫曼树编码就满足前缀码
上面就是使用哈夫曼树进行的编码:
它的编码格式避免了一个元素的码是另一个元素的头部的情况，实用性很强
堆空间的应用实例可以看看的Java内存模型中的堆空间，Java对堆空间在内存中做了很多优化，可以了解一下
