堆
什么是堆
优先队列(Priority Queue):特殊的“队列”，取出元素的顺序是 依照元素的优先权(关键字)大小，而不是元素进入队列的先后顺序
堆的两个特点：
数据对象集:完全二叉树，每个结点的元素值不小于其子结点的元素值
- 任一结点的关键字是其子树所有结点的最大值
-
用数组表示的完全二叉树;
heap.png
heapDemo.png
最大堆的操作
最大堆的插入
核心操作是插到最后一个叶节点后面 相应和父节点比较 交换位置 直到没有父节点大 或者到达哨兵的位置
insertHeap.png
最大堆的删除
核心操作是删除根节点，把最后一个叶节点移到根结点位置上保证树的结构，然后对堆进行正确的排序，比较根节点和子节点的大小，然后做交换操作，直到成为最大堆或者最小堆.
最大堆的建立
建立最大堆:将已经存在的N个元素按最大堆的要求存放在一个一维数组中
方法1:通过插入操作，将N个元素一个个相继插入到一个初 始为空的堆中去，其时间代价最大为O(N logN)。
方法2:在线性时间复杂度下建立最大堆。
- 将N个元素按输入顺序存入，先满足完全二叉树的结构特性
- 调整各结点位置，以满足最大堆的有序特性。 从下面依次往上面建立最大堆或者最小堆。。
哈夫曼树与哈夫曼编码
什么是哈夫曼树
huffmanTree.png
哈夫曼树的构造
每次把权值最小的两棵二叉树合并
哈夫曼树的特点:
- 没有度为1的结点;
- n个叶子结点的哈夫曼树共有2n-1个结点;
- 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树;
- 对同一组权值{w1 ,w2 , ...... , wn}，存在不同构的两棵哈夫曼树
huffmanTree1.png
哈夫曼编码
给定一段字符串，如何对字符进行编码，可以使得该字符串的编码 存储空间最少?
[例] 假设有一段文本，包含58个字符，并由以下7个字符构:a，e，i， s，t，空格(sp)，换行(nl);这7个字符出现的次数不同。如何对 这7个字符进行编码，使得总编码空间最少?
- 用等长ASCII编码:58 ×8 = 464位
- 用等长3位编码:58 ×3 = 174位;
- 不等长编码:出现频率高的字符用的编码短些，出现频率低 的字符则可以编码长些
进行不等长编码前提就是避免二义性，避免二义性的方法就是
前缀码prefix code:任何字符的编码都不是另一字符编码的前缀
可以无二义地解码。
哈夫曼编码就是把带权重的结点通过构造哈夫曼树，然后左0右1 ，有效的编码，无二义性，并且具有最短的wpl
Huffman2.png
