数据结构-浙江大学-堆(六)

什么是堆（heap）

优先队列(Priority Queue)：特殊的“队列”，取出元素的顺序是依照元素的 优先权（关键字） 大小，而不是元素进入队列的先后顺序。

大O记号(上界)
Ω记号(下界)
θ记号（渐近界）

堆：
首先是一个完全二叉树
然后，每一个结点都比子结点大或者小，大的为最大堆。小的为最小堆
特性：从根节点，到下面某一个节点的路径，是一个有序的序列。

插入一个新的元素，由于堆是完全二叉树，自然而然的会放入在[6]的位置

case1 插入的值小于31，正好
case2 插入值的值35大于31，且小于44，插入的31和35值换一下
case3 插入的值58，大于31，大于44，一步一步兑换，58在根的位置

删除最大堆的最大值，也就是58删除
为了保证堆还是一个完全二叉树，考虑将二叉树最后一个元素31移动到根的位置。
31放在根，完全二叉树结构是满足了，但是，根不是最大值了，因此需要调整

最大堆的建立

堆的一个应用：堆排序
用到堆排序，首先我们需要建立一个堆

这种方法说白了就是：
找到倒数第一个有儿子结点的位置，开始调整堆，也就是87-9调整
再调整 30-72-49
再调整 83-55-91
…
循环调整堆

---

哈夫曼树与哈夫曼编码

什么是哈夫曼树

首先看一个栗子：

哈夫曼树的定义

哈夫曼树研究的就是将WPL值最小

哈夫曼树的构造

1、2、3、4、5构造一个哈夫曼树

就是把权值最小的两棵二叉树合并

那么，哈夫曼树的构造也就是如何选出最小的两个值
当然，你可以用查找，查找出最小的两个值，合并最小值，删除两个最小值，将合并的新值插入到原来的列表中。
但是，这种效率没有堆的效率高，因此，我们使用堆来解决选取两个最小值

哈夫曼编码

集合

问题是，如何知道哪个集合大，哪个集合小？也就是如何知道集合的个数？

可以在每个结点中加入一个元素，来记录数的个数，但是，其实只需要在根结点记录个数就行，没必要每个结点都记录，如果非根结点不记录，但是空间还存在，造成空间浪费。
因此，我们利用根结点-1的特性，集合有N个元素，根结点的Parent就记录成-N。