堆及其操作

• 堆
• • 堆的意义与定义
  • 堆的操作
  • • 最大堆的创建
    • 最大堆的创建
• 哈夫曼🌳
• • 哈夫曼🌳的定义
  • 哈夫曼🌳的构造
  • • 重点：这里重点关注N，因为最小堆的元素是删除一个，然后插入一个，这样的话，我们一共N个叶子结点，我们需要执行N-1次操作，，即使H->Size变化，我们的执行次数N-1不变。

堆

堆的意义与定义

定义：“优先队列是特殊的队列，从堆中取出元素的顺序是依照“优先权（关键字）大小，而不是元素进入队列的先后顺序。采用完全二叉树存储的优先队列称为堆””
最大堆：其中元素N（N>0），是一棵完全二叉树，每个结点上的数值大于或等于它的子结点上的元素的值。
操作集：对于任意最多有MaxSize个元素的最大堆（MaxHeap），对于元素item主要的操作：

1. 创建堆的操作：MaxHeap Creat(int MaxSize);
2. 判断堆是否已满的操作:boolean IsFull(MaxHeap H);
3. 插入元素的操作bool Insert(MaxHeap H,ElementType item);
4. 判断堆是否为空的操作:boolean IsEmpty(MaxHeap H);
5. 返回堆中的最大元素(高优先级) :ElementType DeletMax(MaxHeap H);
   采用完全二叉树表示优先队列：堆的两个特性：
   结构性：用数组表示的完全二叉树；
   有序性：根结点到任意结点的关键字序列保持非递增（最大堆）/非递减（最小堆）

堆的操作

最大堆的创建

定义堆类型

//创建最大堆//定义堆的结构类型typedef struct HeapStruct *MaxHeap;struct HeapStruct{ElementType *Elements;//堆是以数组形式存储的int Size;//堆中元素的个数int Capacity;//堆的最大容量}

创建堆函数

MaxHeap Creat(MaxSize)//创建容量为MaxSize的最大堆{MaxHeap H=(MaxHeap)malloc(sizeof(struct HeapStruct));//首先为堆分配一个内存ElementType Elements = (ElementType)malloc((MaxSize + 1)*sizeof(struct ElementType));H->size = 0;//一开始堆为空H->Capacity = MaxSize;H->Elements[0] = MaxData;//定义“哨兵”为大于堆中所有可能元素的值，便于以后更快的操作}

判断堆是否已满

bool IsFull(MaxHeap H){return(H->Size == H->Capacity);}

最大堆元素的插入

bool Insert(MaxHeap H,ElementType X){if(IsFull(MaxHeap H))//判断堆是否已满{printf("堆已满不能继续添加");return False;}//堆不满的情况int i = ++H->Size;//将插入元素放到最大堆的最后一个位置//比较插入元素是否为根结点的最大值for(;X>H->Elements[i/2];i/=2){H->Elements[i] = H->Elements[i/2];}H->Elements[i] = item;return true;//插入元素成功}

判断堆是否为空

//判断堆是否为空bool IsEmpty(MaxHeap H){if (H->Size == 0){return true;}else{return false;}}

最大堆的删除：取出根结点的最大值，同时删除最后一个结点

ElementType DeletMax(MaxHeap H){//判断堆是否为空if (IsEmpty(H)){printf("堆为空不存在元素");return NULL;}//堆不为空的情况int parent=1,child;int MaxResult = H->Elements[parent];int temp = H->Elements[H->Size--];for(parent;2*parent<H->Size;){child = 2*parent;if((child!=H->Size)&&(H->Elements[child]<H->Elements[Child+1]))//判断根结点是否有左右两个子结点；同时如果有两个子结点的话右侧子结点是否大于左侧子结点{child ++;}if(temp>H->Elements[child])//将大的子结点挪到根结点的位置{H->Elements[parent] = H->Elements[child];}else {break;//找到合适的位置并退出}}H->Elements[parent] = temp;return MaxResult;}

最大堆的创建

将已经存在的N个元素按照最大堆的要求存放到一个一维数组中。可以按照最大堆的插入操作。
更简单的创建最大堆的方法：

 1. 将N个元素按照输入的顺序存入二叉树中，不管其有序性 2. 从最后一个元素（H->size/2开始）所在的子二叉树开始，调整各个结点组成的二叉树满足最大堆的有序性。 3.  **重点堆是从第一个元素开始计数的**。 4. 多重for循环，break使得内层包含它的循环直接提前结束，直接就开始了下一次的外循环。！！！

//创建最大堆的过程MaxHeap BuildMaxHeap(MaxHeap H){int i =H->Size/2;//从这个结点向前开始调整int parent,child;for(i;i>0;i--){parent = i;int temp = H->Elements[parent];for(parent;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]){H->Elements[parent] = H->ELements[child];}else{break;}}H->Elements[parent]=temp;}return H;}

哈夫曼🌳

哈夫曼🌳的定义

路径长度：是从树根到某个结点的路径：从根结点开始，沿着某个分支，达到该结点的一个节点序列，路径所含的分支数（该条路径所包含的结点数目-1）。一棵树的路径长度指的是从树根到其余各个结点的路径长度之和。
结点的带权路径指的是：从根结点到该节点之间的路径长度与该结点上所带权值的乘积。

假设：一棵树有N个结点，每个叶结点带有权值W_k,从根结点到每个叶结点的长度为l_k，则每个叶结点的带权路径长度为WPL = ∑ k = 1 n Wk lk \sum_{k=1}^n W_k l_k ∑k=1n​Wk​lk​
假设有n个权值{W₁,W₂,W₃,…,W_N},构造n个叶子的二叉树，每个叶子的权值是n个权值之一，其中众多构成的二叉树中必有一个是带权路径长度最小的，称为最优二叉树（哈夫曼树）。

哈夫曼🌳的构造

由相同权值构成的一组叶节点构成的二叉树具有不同的形态和不同的带权路径长度，如何找到带权路径长度最小的哈夫曼树呢？

一棵二叉树要使其带权路径长度WPL最小，必须使得权值大的叶子结点靠近根节点，而权值小的越远离根结点。将每个字符看成一棵独立的树，每一步执行两棵树的合并，而选择合并的对象是每次选择权值最小的两棵树合并
选择根结点的权值最小和次小的二叉树成为左右子树构成一棵新的二叉树，新二叉树的权值为左右两棵子树的权值之和
然后删除刚刚选择的两棵子树，将新生成的树插入到集合中，当集合中只剩下一棵二叉树的时候，这棵树就是索要建立的哈夫曼树
对于同一组给定权值叶结点所构成的二叉树的形状可能不同但是这些哈夫曼树的带权路径的长度相同，并一定都是最小值

HuffmanTree Huffman(MinHeap H)//H为哈夫曼树类型{//将最小堆按照权值将H调整为最小堆BuildMinHeap(H);int N=H->Size;HuffmanTree T;for(int i=1;i<N;i++){T=(HuffmanTree)malloc(sizeof(struct HTNode));T->left = DeletMin(H);//删除H中的最小结点，成为新的T结点的左节点T->right= DeletMin(H);T->Weight = T->left->Weight+T->right->Weight;Insert(H,T);//将H树中删除两个最小的元素，生成新的元素插入到最小堆中继续进行选择构建}return DeletMin(H);}

重点：这里重点关注N，因为最小堆的元素是删除一个，然后插入一个，这样的话，我们一共N个叶子结点，我们需要执行N-1次操作，，即使H->Size变化，我们的执行次数N-1不变。