数据结构篇（五）：

2024-02-06 08:50:40

数据结构篇（五）：

文章目录

数据结构篇（五）：

1.这里我们先来了解堆的概念。

什么是堆呢？

了解堆之前，首先我们让看看优先队列：特殊的“队列”，取出元素的顺序是按照元素的优先级大小，而不是元素进入队列的先后顺序。

我们怎么对优先队列进行管理呢？

我们要进行的的操作是在队列中插入新的任务，还有当CPU空缺出来以后，选择优先级最高的放入CPU中。

若是采用数组或链表实现优先队列
数组实现如下：

插入——元素总是插入尾部

删除——查找最大（或最小关键字），从数组中删去需要移动的元素

链表实现如下：

插入：元素总是插入链表的头部

删除：查找最大（最小）关键字删去结点

因为数组每次删除元素之后还需要进行后续元素的移动，而链表只需要改父节点的指针，所以相比之下还是链表比较方便。

有序数组：

插入：找到合适的位置，移动元素并插入

删除：删去最后一个元素

有序链表：

插入：找到合适的位置插入元素

删除：删除首元素或最后元素

上述四种问题在很大的范围内可以解决我们的问题，然而学了这么久的树我们是不是也可以采用二叉树来存储结构呢？

如果我们想删除最大最小值，那么我们就等于遍历树的左子树和右子树，时间效率就是树的高度。

但是简单的使用这种方法往往会带来许多问题。

如果我们一直遍历右子树删除，那会发生什么？

树歪了，即右边子树都删完了，左边子树还剩长长的一条，此时的时间效率就不是树的高度了。

所以这里我们要用完全二叉树进行存储，并且它的每个节点都比它左右所有结点的值大或小，这样也就形成了我们说讨论的堆。

最大堆：

它的每个节点都比它左右所有结点的值大

最小堆：

它的每个节点都比它左右所有结点的值小

不是堆：

不满足最大堆和最小堆的情况的条件（这里15小于16，与最小堆矛盾）。

这里注意：从根结点到任意结点路径上结点序列的有序性。

让我们看看最大堆是如何实现的

最大堆：

最大堆的创建和插入

typedef struct HeapStruct *MaxHeap;
struct HeapStruct
{
    ElementType *Elements; //存储堆元素的数组
    int Size;	//堆中元素个数
    int Capacity; //堆的容量
}
MaxHeap Creat(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;
}

如果插入结点小于当前结点：

如图，插入20小于31，所以直接插入就好。

如果插入结点大于当前结点：

此时有序性被破坏了，所以我们需要将其35和31调换位置。

插入结点数值大于其好多父节点：

如图，此时插入58，比31和44都大，所以我们进行换位：

以上操作可表示为下述代码：

void Insert(MaxHeap H,ElementType item)
{
    int i;
    if(IsFull(H))
    {
        printf("最大堆已满");
        return;
    }
    i = ++H->Size;
    for(;H->Elements[i/2]<item;i/=2)  //item与当前结点比较
        H->Elements[i] = H->Elements[i/2]; //向下过滤节点
    H->Elements[i] = item; //插入结点
}

还记得我们之前创建堆里放的那个哨兵吗？此时我们我们在for这里就用上了。原本我们还需要设立一个条件判断防止我们越过树的根结点，但是此时我们设置了哨兵，在检测到哨兵时我们就自动知道了到达树的顶上了，就可以做相关操作防止溢出，并大大提高了我们的效率。

最大堆的删除

ElementType DeleteMax(MaxHeap H)
{
    int Parent,Child;
    ElementType MaxItem,temp;
    if(IsEmpty(H)) //判断堆空不空
    {
        printf("最大堆已空");
        return ;
    }
    MaxItem = H->Elements[1];	//存储要删除的根结点
    temp = H->Elements[H->Size--]
    //最大堆的最后一个元素向上过滤结点
    for(Parent = 1;Parent*2<=H->Size;Parent = Child)
    {
        //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->Element[Child];
        //将左右儿子中较大者换上来，并在下一次循环将当前结点换下去
    }
    H->Elements[Parent] = temp;
    return MaxItem;
}

如图

我们想删除58这个结点，按照之前的知识点我们肯定是取31这个结点来代替它（左子树最大值）

可见，此时完全二叉树的特性保留了，但是树的有序性（根为最大值）无法保证。此时我们发现44>31,35>31,所以换位置

得到上图。

最大堆的建立

建立最大堆:将已经存在的N个元素按最大堆的要求存放在一个一维数组中

方法1:

通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中去，其时间代价最大为O(N logN)。

方法2:

在线性时间复杂度下建立最大堆。
(1)将N个元素按输入顺序存入，先满足完全二叉树的结构特性
(2）调整各结点位置，以满足最大堆的有序特性。

方法如下：

我们从底下开始做，首先我们找到倒数第一个由儿子的结点，即87（因为保证左右边只有一个儿子）。

随后

先将小蓝框里的结点依次转换为堆，再将红框的结点转换为堆。

效果如上。

堆的知识大致如上。

接下来让我们讲讲哈夫曼树和哈夫曼编码。

2.哈夫曼树和哈夫曼编码

哈夫曼树的介绍：

正如我们所知每个ASCLL码用7位进行编码，如果有一篇文章，它有若干个字符构成，每个abcd都用7位进行编码，如果这篇文章由1万个字符，则需要7万位斤进行编码。

但是我们知道每个字符在文章里出现的频率是不一样的，比如说e这个字符，它出现的频率大于许多其他字符。如果此时我们能对他进行5位编码，对一些不常见的字符用7、8位进行编码，我们处理起来的效果是不是更好呢？

这就是哈夫曼树和哈夫曼编码所讨论的问题。

例：

比如我们对考试成绩进行5分制转换：

由上表我们可以得到如下树结构：

正如我们所看到的，对60分的成绩，只需要判断一次，但是对90分的成绩，我们需要判断四次，如果此时60分的人很少，90分的人很多，则是不是意味着做四步判断的人更多，这样的转换效果就不太好，如果给出各分数段频率

其效率为：

0.05×1+0.15×2+0.4×3+0.3×4+0.1×4 = 3.15

同样是上述的题，但是我们换种树的结构：

此时它的效率为：

0.05×3+0.15×3+0.4×2+0.3×2+0.1×2 = 2.2

效果是不是比上一个结构好很多？

所以这样我们就可以得出一个结论，我们需要根据结点不同的查找频率构造更有效的搜索树。这就是哈夫曼树和哈夫曼编码所要解决的问题。

哈夫曼树又称最优树，每个叶节点的权值×叶节点到根节点的长度累加起来，这个值就叫带权路径的长度（WPL）。

哈夫曼树就是想把带权路径长度调整到最小。

哈夫曼树的构造：

哈夫曼树的构造就是：每次把每个结点的权重，从小到大排序，再把权值最小的两颗树并在一起。

例：

我们将权值12345排序好了，然后合并权值最小的结点：

此时产生了一个新节点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); //将权值调整为最小堆
    for(i = 1;i<H->Size;i++)
    {
        T = malloc(sizeof(struct TreeNode));
        T->Left = DeleteMin(H);
        T->Right = DdeleteMin(H);
        //		删除权值最小的结点，做为新T的左右子结点
        T->Weight = T->Left->Weight+T->Right->Weight;
        //		计算新权值
        Insert(H,T);
        //   	插入新权值
    }
    T = DeleteMin(H);		//合并完的树根
    return T;
}

哈夫曼树的特点：

1.没有度为1的结点

2.n个叶子结点的哈夫曼树共有2n-1个结点

3.哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树

n0:叶结点总数

n1:只有一个儿子的结点总数

n2:有2个儿子的结点总数

n2 = n0-1

4.同一组权值，构成两组不同构的哈夫曼树

例：权值为{1，2，3，3}