数据结构篇(五):

数据结构篇(五):

文章目录

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}
        数据结构篇(五):
          数据结构篇(五):

就有以上两种情况的结构。

​   第一个是1、2并再跟3并再跟3并

​   第二个是1、2并,3、3并,再合并

但是他们的WPL值是一样的.

哈夫曼编码:

我们先来考虑一个问题:

​   给定一段字符串,我们如何对字符进行编码,使字符串的编码存储空间最小?

我们用一道例题来讨论这个问题。

例:

​   假设有一段文本,包含58个字符,并由以下7个字符构:a、e、i、s、t、空格(sp)、换行(nl),这7个字符出现的次数不同。如何对这7个字符进行编码,使得总编码空间最少?

分析:

​   (1)用ASCLL编码:58×8 = 464位

​   (2)用等长3位编码:58×3 = 174位

​   (3)不等长编码:频率高的短,频率低的长

    ASCLL码和等长3位编码都出来了,那么我们怎么实现不等长编码呢?

例:

​   a:1 e:0 s:10 t:11… 根据左边的编码规则,我们怎么表示1011的编码呢?显然这是有问题的。

数据结构篇(五):

​   如图,一个1011产生了3种编码格式,这种情况称为编码的二义性。

我们如何避免二义性呢?

​   前缀码,即任何字符的编码都不是另一字符编码的前缀。

​   用上述的例子来讲就是,a:1 s:10,此时a就等于s的前缀了,这样就会出现我们说讲的二义性。

​   在数的结构中,如果我们的编码全是叶节点,就不会有二义性。

例:

        数据结构篇(五):

​   上图,其编码全在叶节点上,所以没有二义性。
数据结构篇(五):
          数据结构篇(五):

由图,此结构的WPL为16

  如下也是同样的道理:
数据结构篇(五):
  涓滴之水终可磨损大石,不是由于它力量大,而是由于昼夜不舍的滴坠。只有勤奋不懈的努力才能够获得那些技巧,因此,我们可以确切地说:说:不积跬步,无以致千里。

以上就是本文全部内容。

数据结构篇(四):_风声向寂的博客-CSDN博客

数据结构篇(三):_风声向寂的博客-CSDN博客

数据结构篇(二):_风声向寂的博客-CSDN博客

数据结构篇(一):_风声向寂的博客-CSDN博客

上一篇:teb_local_planner/Tutorials


下一篇:二叉堆