数据结构——被优先队列玩起来的“树“

2024-02-01 04:30

本文主要是介绍数据结构——被优先队列玩起来的“树“,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

树——最终篇

    • ⭐⭐⭐
    • 什么是堆🌊🌊
      • ✅什么是优先队列
      • ✅优先队列的重要性
      • ✅优先队列和堆的暧昧关系
      • ✅回忆完全二叉树
      • ✅二叉堆
      • ✅举点栗子
      • ✅二叉堆的特性
    • 堆的抽象数据类型描述(最大堆演示带入)🌊🌊
      • ✅堆的主要操作
      • ✅最大堆的创建
      • ✅最大堆的插入
      • ✅最大堆的删除
    • 手动模拟堆⭐⭐⭐
    • 参考代码(C++版本)
      • ✅模块化剖析
        • heap_swap ✨ ✨ ✨
        • down(int u)
        • up(int u)
    • 树和森林与二叉树的转换🌊🌊
      • ✅树转换为二叉树
      • ✅森林转换为二叉树
      • ✅二叉树转换为树
      • ✅二叉树转换为森林
    • 哈夫曼树和哈夫曼编码🌊🌊
      • ✅日常瞎叭叭叭点闲话
      • ✅哈夫曼树的定义
    • 哈夫曼树的构造
      • 参考实现代码
      • ✅总结哈夫曼树的特点
    • 哈夫曼编码
      • ✅哈夫曼编码的生成方式
  • 写在最后🎈🎈🎈
    • 若有偏僻,欢迎各位小伙伴及时雅正( ^ - ^ )
    • 持续更新对数据结构的总结和理解喔💖~
      • 小伙伴们都应该也在备战期末了,笔者也在慢慢备考,更文就会慢一点点哈,原谅我。期末加油~ 🌹🌹🌹

小伙伴看完中篇的BST树和AVL树可能会觉得,树也太折腾人了,放过孩子吧。最终篇是不是要甩大招了喃,不😭,😭😭

最终章了,主要的设计是为了对付那人人得而诛之的期末考试,我下面所总结的内容,除了堆会在算法竞赛中用到,其他两个就让它们在期末考试的舞台上蹦跶吧,可恶的考试 💔

考试

⭐⭐⭐

什么是堆🌊🌊

✅什么是优先队列

优先队列(Priority Queue):一种特殊的队列,取出元素的顺序是依照元素的优先权(关键字)大小,而不是元素进入队列的先后顺序

经验出发,我们可以用数组实现、也可以用链表实现,下面我们通过一张图看看它们的实现效果
效果对比

通过对比可以看出来,要么时间复杂度过高,要么就只是在某一种操作上很突出,其他操作又相对难受了,整体都是不太尽人意。那么是否可以采用二叉树存储结构?假如二叉树的结点数是n,那么一棵完全二叉树的树高就是logN。利用这一性质,确实可以实现高速的管理数据

✅优先队列的重要性

优先队列

✅优先队列和堆的暧昧关系

优先队列

能够完成下列操作的数据结构叫做优先队列

  1. 插入一个数组
  2. 取出最值(能获得数值,能实现删除)

示意图

能够使用二叉树高效解决上述问题的数据结构被称为堆

✅回忆完全二叉树

没有满二叉树那么完美,最后可能会缺一些子树,但是一定一定要保证子树是按照层序编号排列的二叉树
完全二叉树

✅二叉堆

如果一棵完全二叉树各结点的键值与一个数组的各元素具备如图所示的对应关系,那么这个完全二叉树就是二叉堆。
二叉堆

二叉堆的逻辑结构是完全二叉树,但是实际却是一个用1作为起点的一维数组来表示的

若将表示二叉堆的数组命名为A,二叉堆的元素大小(元素个数)为H,那么二叉堆的元素就存储在A[1,…,H]中,其中根的下标为1.当给定一个结点的下标i时,就可以通过i/2、2 * i 、 2 * i +1轻松的算出来其父结点parent(i)、左子结点left(i)、右子结点right(i)。

✅举点栗子

二叉堆的一些栗子

✅二叉堆的特性

  1. 结构性:用数组表示的完全二叉树;
  2. 有序性:任一结点的关键字是其子树所有结点的最大值(或最小值)
    1. “最大堆(MaxHeap)”,也称“大顶堆”:最大值
    2. “最小堆(MinHeap)”,也称“小顶堆” :最小值

最大堆的根中存储着最大元素,回看二叉堆的图,可以看出来它就是一个最大堆

堆的抽象数据类型描述(最大堆演示带入)🌊🌊

✅堆的主要操作

最大堆 MaxHeap H,元素ElementType item

  1. MaxHeap Create( int MaxSize ):创建一个空的最大堆。
  2. Boolean IsFull( MaxHeap H ):判断最大堆H是否已满。
  3. Insert( MaxHeap H, ElementType item ):将元素item插入最大堆H。
  4. Boolean IsEmpty( MaxHeap H ):判断最大堆H是否为空。
  5. ElementType DeleteMax( MaxHeap H ):返回H中最大元素(高优先级)。

✅最大堆的创建

struct HeapStruct{int Capacity;//堆的最大容量 int Size;//堆的当前元素个数 ElementType *Elements;//存储堆元素的数组 
};MaxHeap Create( int MaxSize )
{//创建一个容量为MaxSize的空的最大堆MaxHeap H = malloc(sizeof(struct HeapStruct));H->Elements = malloc((MaxSize + 1) * sizeof (ElementType));H->Size = 0;H->Capacity = MaxSize;H->Elements[0] = MaxData;//在数组没有用到0号索引处放置一个哨兵。待会再理解为什么要放置它 return H;
} 

✅最大堆的插入

操作流程:

  1. 将这个新的元素插入到堆的最后一个元素,因为是用数组实现的堆,在数组的末尾直接修改数组的长度就可以实现插入或者删除操作。

  2. 将其和它的父结点作比较,倘若它的数值比根节点的大,它就往上走,再比较,直到调整为符合二叉堆的性质为止。

void Insert(MaxHeap H, ElementType item) //将元素item插入最大堆H,其中H->Elements[0]已经定义为哨兵
{int i;if(IsFull(H))  {printf("堆已满");return ;}i = ++H->Size;//i指向插入后堆中的最后一个元素的位置for(; H->Elements[i/2] < item;i /= 2) H->Elements[i] = H->Elements[i/2];//向上调整。将这个插入的数据调整到合适它的位置H->Elements[i]  = item;//将item插入 
} 

H->Element[ 0 ] 是哨兵元素,它不小于堆中的最大元素,控制顺环结束。在加了哨兵来控制循环的结束以后,我们要考虑的内容就减少到怎么实现逻辑,不用多花时间去想循环要执行多少次
哨兵

✅最大堆的删除

删除思路和插入是类似的,因为二叉堆的本质是用数组模拟的,删除数组的最后一位是很容易的,直接数组长度长度就可以了,所以这里的思路是用数组的最后一个元素替代要删除的元素,再调整

ElementType DeleteMax(MaxHeap H) 
{int Parent ,Child;//代表两个指针,分别指向父结点和子结点 ElementType MaxItem,temp;if(IsEmpty(H)) {printf("最大堆为空");return ;}MaxItem = H->Elements[1];//取出根节点的最大值temp = H->Elements[H->Size--] ;//获取最大堆的最后一个元素从根节点Parent开始过滤 for(Parent = 1;Parent * 2 <= H->Size;Parent = Child){Child = Parent * 2;if((Child != H->Size) && (H->Elements[Child] < H->Elements[Child+1])) Child ++;//Child指向左右子结点的较大者if(temp >= H->Elements[Child]) break;//满足最大堆的要求了,调整结束 else H->Elements[Parent] = H->Elements[Child];}H->Elements[Parent] = temp;return MaxItem;
}

手动模拟堆⭐⭐⭐

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 ✨ ✨ ✨

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. 层次调整:以根结点为圆心,每个结点顺时针旋转到看起来舒服的位置就好
    层次调整

✅森林转换为二叉树

森林是由若干树组成的,所以完全可以理解为,森林中的每一棵树都是兄弟,我们可以按照处理兄弟的处理方式来操作。

  1. 把森林中每一棵树转换二叉树
  2. 第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树的右孩子
    森林转二叉树

✅二叉树转换为树

  1. 加线:如果某个结点的左孩子有右子树,让该结点和其左孩子的右子树的右分支上各结点连起来
  2. 去线:去掉原二叉树中所有结点与其右子树的连线
  3. 调整
    二叉树转树

✅二叉树转换为森林

  1. 特判。只看这棵二叉树的根结点有没有右孩子,有就是森林,没有就是一棵树
  2. 从根结点连线,若右孩子存在,就把它与右孩子的线去掉
  3. 看看分出的二叉树,若右孩子存在,就继续删除连线,直到没有👀
    二叉树转森林

哈夫曼树和哈夫曼编码🌊🌊

✅日常瞎叭叭叭点闲话

哈夫曼编码了,笔者目前也没有在竞赛题或者面试题中看到,但是期末考试好像要考吧~,所以这里梳理了一下,考试的时候解决它就行。前辈们发明的创世之作,感觉现在还拿捏不住
拿捏不住

✅哈夫曼树的定义

  1. 路径:从树中一个结点到另一个结点之间的分支构成两个结点之间的路径
  2. 路径长度:路径上分支数目
  3. 树的路径长度:树根到每一个结点的路径长度之和
    路径的长度

如上图所示,第一个图中,根结点到D结点的路径长度是4。第二个图中,根结点到D结点的路径长度是2

如果考虑带权的结点,结点的带权路径长度为从该结点到树根之间的路径长度与权值的乘积。

哈夫曼树:设二叉树有n个叶子结点,每个叶子结点带有权值 wk,从根结点到每个叶子结点的长度为 lk,则其中带权路径长度WPL最小的二叉树。

哈夫曼树的构造

每次把权值最小的两棵二叉树合并。

  1. 将给定的n个权值{w1,w2,…,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,…,Tn},其中每棵树只有一个根节点。也就是把每个权值单独放在一个结点中,直接作为一棵树
  2. 森林中选取两棵树中根结点权值最小的的二叉树作为左右子树构造一棵新的二叉树,新的二叉树的根结点权值为原来两棵树根结点的权值和
  3. 在森林中将被选取的两个根节点从森林中删除,将新构建的二叉树加入到森林中
  4. 重复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. 没有度为1的结点;
  2. n个叶子结点的哈夫曼树共有2n-1个结点
  3. 哈夫曼树的任意非叶节点的左右子树交换后仍是哈夫曼树
  4. 对同一组权值{w1 ,w2 , …… , wn},存在不同构的两棵哈夫曼树
    不同构

哈夫曼编码

哈夫曼编码是一种用于使编码总长最短的编码方案。目的也很直接,压缩数据存储和传输的成本,就可以省钱啦~
没钱了

✅哈夫曼编码的生成方式

  1. 构造哈夫曼树,设需要编码的字符集合为{d1,d2,…,dn},它们在电文中的权重集合为{w1,w2,…,wn},以d1,d2,…,dn作为叶子结点,w1,w2,…,wn作为它们的权值,构造一棵哈夫曼树
  2. 在哈弗曼树上求叶子结点的编码。规定哈夫曼树中的左分支代表0,右分支代表1,则从根结点到每个叶子结点所经过的路径分支组成的0和1的序列便是该结点的对应字符的不等长编码。

写在最后🎈🎈🎈

若有偏僻,欢迎各位小伙伴及时雅正( ^ - ^ )

持续更新对数据结构的总结和理解喔💖~

小伙伴们都应该也在备战期末了,笔者也在慢慢备考,更文就会慢一点点哈,原谅我。期末加油~ 🌹🌹🌹

高分

这篇关于数据结构——被优先队列玩起来的“树“的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/666082

相关文章

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi

Java并发编程之——BlockingQueue(队列)

一、什么是BlockingQueue BlockingQueue即阻塞队列,从阻塞这个词可以看出,在某些情况下对阻塞队列的访问可能会造成阻塞。被阻塞的情况主要有如下两种: 1. 当队列满了的时候进行入队列操作2. 当队列空了的时候进行出队列操作123 因此,当一个线程试图对一个已经满了的队列进行入队列操作时,它将会被阻塞,除非有另一个线程做了出队列操作;同样,当一个线程试图对一个空

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访