手动模拟堆
C++选手确实可以直接调用STL容器中的priority_queue实现优先队列。和queue一样，push()用于向队列中插入一个元素，top()用于访问(读取)开头元素，pop()用于删除开头元素。在priority_queue中，开头元素永远是拥有最高优先级的元素。
对于没有这个库函数的选手，可以练习如何手写堆
参考代码(C++版本)
#include <iostream> #include <algorithm> #include <string.h> using namespace std; const int N = 100010; int h[N], ph[N], hp[N], cnt; void heap_swap(int a, int b) { swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); } void down(int u) { int t = u; if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1; if (u != t) { heap_swap(u, t); down(t); } } void up(int u) { while (u / 2 && h[u] < h[u / 2]) { heap_swap(u, u / 2); u >>= 1; } } int main() { int n, m = 0; scanf("%d", &n); while (n -- ) { char op[5]; int k, x; scanf("%s", op); if (!strcmp(op, "I")) { scanf("%d", &x); cnt ++ ; m ++ ; ph[m] = cnt, hp[cnt] = m; h[cnt] = x; up(cnt); } else if (!strcmp(op, "PM")) printf("%d\n", h[1]); else if (!strcmp(op, "DM")) { heap_swap(1, cnt); cnt -- ; down(1); } else if (!strcmp(op, "D")) { scanf("%d", &k); k = ph[k]; heap_swap(k, cnt); cnt -- ; up(k); down(k); } else { scanf("%d%d", &k, &x); k = ph[k]; h[k] = x; up(k); down(k); } } return 0; }
模块化剖析
heap_swap
int ph[N];//ph是从指针数组指向堆heap，存的是第k个插入的数在堆里面下标是多少 int hp[N];//hp就是从堆heap映射到指针，堆里面的某一个点是第几个插入的点
手动实现堆最主要的就是实现它的交换。为此，我们额外开了两个数组。代表从指针数组pointer指向堆heap的数组ph 。 以及代表从堆heap指向指针数组pointer的hp数组。
因为是用数组模拟的堆，在使用指针的思想进行定位的时候，我们利用ph数组中存的索引下标定位到它在堆中的位置。也可以通过堆中的点，找回来它在数组中的索引
////
down(int u)
对这个传入的位置进行向下调整。假如它的左右孩子存在，并且比它这个父结点小，就把父结点交换下去。
int t = u; if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
up(int u)
当传入的位置的父结点存在，而且这个位置中的数据比父结点中的数据大，就将这个位置和父结点交换，实现向上调整
while (u / 2 && h[u] < h[u / 2]) { heap_swap(u, u / 2); u >>= 1; }
树和森林与二叉树的转换
树转换为二叉树
步骤：
1.加线:把除根节点之外的所有兄弟结点连起来
2.去线：把除长子(最左边的结点)以外的其他孩子结点之间的线去掉
3.层次调整：以根结点为圆心，每个结点顺时针旋转到看起来舒服的位置就好
森林转换为二叉树
森林是由若干树组成的，所以完全可以理解为，森林中的每一棵树都是兄弟，我们可以按照处理兄弟的处理方式来操作。
- 把森林中每一棵树转换二叉树
- 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的右孩子
二叉树转换为树
- 加线：如果某个结点的左孩子有右子树，让该结点和其左孩子的右子树的右分支上各结点连起来
- 去线：去掉原二叉树中所有结点与其右子树的连线
- 调整
二叉树转换为森林
特判。只看这棵二叉树的根结点有没有右孩子，有就是森林，没有就是一棵树
从根结点连线，若右孩子存在，就把它与右孩子的线去掉
看看分出的二叉树，若右孩子存在，就继续删除连线，直到没有👀
哈夫曼树和哈夫曼编码
哈夫曼树的定义
- 路径：从树中一个结点到另一个结点之间的分支构成两个结点之间的路径
- 路径长度：路径上分支数目
- 树的路径长度：树根到每一个结点的路径长度之和
如上图所示，第一个图中，根结点到D结点的路径长度是4。第二个图中，根结点到D结点的路径长度是2
如果考虑带权的结点，结点的带权路径长度为从该结点到树根之间的路径长度与权值的乘积。
哈夫曼树：设二叉树有n个叶子结点，每个叶子结点带有权值 wk，从根结点到每个叶子结点的长度为 lk，则其中带权路径长度WPL最小的二叉树。
哈夫曼树的构造
每次把权值最小的两棵二叉树合并。
- 将给定的n个权值{w1,w2,…,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,…,Tn},其中每棵树只有一个根节点。也就是把每个权值单独放在一个结点中，直接作为一棵树
- 森林中选取两棵树中根结点权值最小的的二叉树作为左右子树构造一棵新的二叉树，新的二叉树的根结点权值为原来两棵树根结点的权值和
- 在森林中将被选取的两个根节点从森林中删除，将新构建的二叉树加入到森林中
- 重复2 和 3操作
参考实现代码
//注：这只是核心流程的代码，部分函数这里没有附上的~ typedef struct TreeNode *HuffmanTree; struct TreeNode{ int Weight; HuffmanTree Left , Right; }; HuffmanTree Huffman(MinHeap H) { //假设H->Size个权值已经存在H->Elements[]->Weight里 int i; HuffmanTree T; BuildMinHeap(H);//将H->Elements[]按权值调整为最小堆 for(i = 1; i < H->Size;i++) //做 H->Size -1 次合并 { T = malloc(sizeof (struct TreeNode)) ; T->Left = DeleteMin(H);//从最小堆中删除一个结点，作为新T的左子结点 T->Right = DeleteMin(H) ;//最小堆中删除一个结点，作为新T的右子结点 T->Weight = T->Left->Weight + T->Right->Weight;//计算新的权值 Insert(H,T) ;//将新的T插入到最小堆 } T = DeleteMin(H) ; return T; }
总结哈夫曼树的特点
- 没有度为1的结点；
- n个叶子结点的哈夫曼树共有2n-1个结点
- 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树
- 对同一组权值{w1 ,w2 , …… , wn}，存在不同构的两棵哈夫曼树
哈夫曼编码
哈夫曼编码是一种用于使编码总长最短的编码方案。目的也很直接，压缩数据存储和传输的成本，就可以省钱啦~
哈夫曼编码的生成方式
- 构造哈夫曼树，设需要编码的字符集合为{d1,d2,…,dn},它们在电文中的权重集合为{w1,w2,…,wn},以d1,d2,…,dn作为叶子结点，w1,w2,…,wn作为它们的权值，构造一棵哈夫曼树
- 在哈弗曼树上求叶子结点的编码。规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶子结点所经过的路径分支组成的0和1的序列便是该结点的对应字符的不等长编码。
