二叉树:堆的建立和应用

ops/2024/11/28 19:04:32/

在建立堆之前,我们要知道什么是树和二叉树

树是一种非线性的数据结构,它是由n(n>0)个结点组成的一个具有层次关系的集合,之所以把它叫做树,是因为它长得像一棵倒挂的树,也就是根在上面,叶子在下面

树形结构

树形结构的特性: 

1、树里面有一个特殊的结点,叫做根结点,它没有前驱结点

2、除了根结点以外的结点又分为m(m>0)个集合,其中每一个集合又是一棵与树结构类似的子树,而且每棵子树的根结点都有一个且只有一个前驱结点,但可以有多个或0个后继结点

3、在树形结构中,子树之间不能有交集,否则就不是树形结构

4、除了根结点,每个结点有且只有一个父结点

5、一棵n个结点的树有n-1条边

下面是一些与树相关的术语

⽗结点/双亲结点:若⼀个结点含有⼦结点,则这个结点称为其⼦结点的⽗结点
⼦结点/孩⼦结点:⼀个结点含有的⼦树的根结点称为该结点的⼦结点; 
结点的度:⼀个结点有⼏个孩⼦,他的度就是多少;
树的度:⼀棵树中,最⼤的结点的度称为树的度;
叶⼦结点/终端结点:度为 0 的结点称为叶结点
分⽀结点/⾮终端结点:度不为 0 的结点;
兄弟结点:具有相同⽗结点的结点互称为兄弟结点(亲兄弟);
结点的层次:从根开始定义起,根为第 1 层,根的⼦结点为第 2 层,以此类推;
树的⾼度或深度:树中结点的最⼤层次;
结点的祖先:从根到该结点所经分⽀上的所有结点
路径:⼀条从树中任意节点出发,沿⽗节点-⼦节点连接,达到任意节点的序列;
⼦孙:以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙;
森林:由 m m>0 ) 棵互不相交的树的集合称为森林;

非树形结构 

 树的表示

树的结构相比于线性表要复杂点,存储起来也会比较麻烦,又要保存值,又要保存结点与结点之间的关系

在这里我们用一种比较常用的表示方法:孩子兄弟表示法

struct TreeNode
{struct Node* child; // 左边开始的第⼀个孩⼦结点struct Node* brother; // 指向其右边的下⼀个兄弟结点int data; // 结点中的数据域
};

树形结构实际运用场景

⽂件系统是计算机存储和管理⽂件的⼀种⽅式,它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中,树结构被⼴泛应⽤,它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间的关联。

 

 二叉树

在树形结构中我们最常用的就是二叉树,一棵二叉树是结点的一个有限集合,这个集合是由一个根结点加上两棵分别称为左子树和右子树的二叉树组成

二叉树的特点

1、二叉树不存在度大于2的结点;

2、二叉树的子树有左右之分,顺序不能颠倒,所以二叉树是一棵有序树

 当然二叉树的结构不单单就上面一种情况

 现实中也存在这种结构的树

特殊的二叉树:满二叉树、完全二叉树

满二叉树:一棵二叉树,如果每一层的结点数都达到最大值,则这棵二叉树就是满二叉树

比如一棵二叉树的层数为h,且它的结点总数是2^k-1,则它就是满二叉树

 完全二叉树:完全二叉树就是除了最后一层,其他层数的结点数都达到最大的一种二叉树,满二叉树是一种特殊的完全二叉树,完全二叉树是一种效率很高的数据结构

 二叉树的特性

1、当根结点的层数为1,则一棵非空二叉树的第h层上最多有2^(h-1)个结点

2、当根结点的层数为1,则深度为h的二叉树的总结点数为2^h-1;

3、当根结点的层数为1,结点数为n的满二叉树的深度h=log2(n+1)(以2为底,n+1为对数)

二叉树的存储结构 

二叉树可以使用两种结构存储:顺序存储、链式存储

我们在这里主要讲解二叉树的顺序结构存储,在前面数据结构的学习中我们得知顺序结构是使用数组来存储,而完全二叉树十分适用于顺序结构存储,因为这样不会有空间的浪费

而如果其他的二叉树使用顺序结构存储,就会造成空间的浪费

 在数据结构中,我们通常把堆(一种二叉树)使用顺序结构的数组来存储,但要注意的是这里堆和操作系统中的堆是两回事,一个是数据结构,一个是操作系统中内存管理内存的一块区域分段

概念

堆是一种特殊的二叉树,具有二叉树的特性的同时,还具备一些特性:堆分为大堆/大根堆、小堆/小根堆;我们把根结点最大的堆叫做大堆/大根堆把根结点最小的堆叫做小堆/小根堆

 堆的特性

1、结点下标为i(i>0)的父结点下标为:(i-1)/2,i=0就表示为根结点,它没有父结点;

2、结点下标为i(i>0)的左孩子下标为:2*i+1;右孩子下标为:2*i+2,当它们的i下标超过总结点数,就不存在孩子结点

 堆的实现

向上调整算法

堆的向上调整算法使用的前提是:在插入新元素之前,前面的元素就已经满足了堆的性质!!

它的本质思想(建小堆):

1、将新元素插入到叶子节点;

2、与它的父结点进行比较,如果小于父结点的值,就交换;

3、把原本父结点下标当作子结点,在进行步骤2,与现在下标的父结点进行比较,重复该步骤

结束条件结点到达根结点位置或者提前调整到合适的位置,满足了堆的特性

void Swap(int* x, int* y)
{int temp = *x;*x = *y;*y = temp;
}//向上调整算法
void AdjustUp(HPDataType* a, int child)
{assert(a);int parent = (child - 1) / 2;while (child>0){if (a[child] < a[parent])//建小堆{Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

向下调整算法

向下调整算法的前提是左右子树都符合堆的条件

它的本质思想(建小堆):

1、从根结点开始,与它的左右结点中较小的进行比较,如果小于子结点的值就交换值;

注:要考虑两个子结点的大小的比较,而且右孩子结点的下标不能大于总结点数

2、交换后的子结点作为父结点重复上面步骤

直到孩子结点下标大于或等于总结点数

//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);int child = parent * 2 + 1;while (child<n){if (child+1 < n && a[child] > a[child + 1])//先找孩子结点{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

结构

堆是使用顺序结构存储的,所以它的结构和顺序表的结构相同

typedef int HPDataType;typedef struct Heap 
{HPDataType* arr;int size;int capacity;
}HP;

初始化和销毁

初始化和销毁也和顺序表一样

//初始化
void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capacity = 0;
}//销毁
void HPDestroy(HP* php)
{assert(php);if (php->arr){free(php->arr);}php->arr = NULL;php->capacity = php->size = 0;
}

插入

堆的插入是将数据插入到数组的尾部,然后再进行调整,使它满足堆的特性(大堆或小堆)

//堆的插⼊
void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* temp=(HPDataType*)realloc(php->arr, sizeof(HPDataType) * newcapacity);if (temp == NULL){perror("realloc fail!\n");exit(1);}php->arr = temp;php->capacity = newcapacity;}php->arr[php->size] = x;AdjustUp(php->arr, php->size);php->size++;
}

所以,堆的插入就分为两步:先插入,再调整 

删除

堆的删除是删除堆顶的数据,将堆顶的数据和最后一个结点的数据交换,这时堆顶数据就到了数组的尾部,直接删除数组的最后一个数据就行,删完了以后,就需要将现在的二叉树调整为堆结构

// 判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}
//堆的删除
void HPPop(HP* php)
{assert(php);assert(!HPEmpty(php));Swap(&php->arr[0], &php->arr[php->size-1]);php->size--;AdjustDown(php->arr, php->size, 0);
}

 

取堆顶元素和堆的数据个数

// 取堆顶的数据
HPDataType HeapTop(Heap* php)
{assert(php);assert(!HeapEmpty(php));return php->arr[0];
}// 堆的数据个数
int HeapSize(Heap* php)
{assert(php);return php->size;
}

堆的应用

堆排序

堆排序是借助堆的算法思想,而不是直接使用堆的数据结构来实现

堆排序的时间复杂度为:O(nlogn)

堆排序的实现思想:

1、先将传入的数组建成堆(升序建大堆,降序建小堆);

2、交换堆顶元素和堆尾元素;

3、对数组进行向下调整,使其保持堆的特性;

4、重复2和3的步骤,直到要调整的元素为1时结束,排序完成

在这里演示一个堆排序实现降序

这里的end一开始就为最后一个元素的下标,也是要调整元素个数,每次调整后要减减,也就是往前移

向下调整算法需要调整的就是元素的个数,所以是先调整,再end--

 代码为

#include"HeapSort.h"void HeapSortUp(int* arr,int n)//向上调整算法建堆:时间复杂度O(nlogn)
{//排升序建大堆//排降序建小堆//先建堆for (int i = 0; i < n; ++i)//这里建的堆是大堆{AdJustUp(arr, i);}//再排序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);//交换堆顶和尾结点AdJustDown(arr, 0, end);end--;}}
void HeapSortDown(int* arr, int n)//向下调整算法建堆:时间复杂度O(n)
{//排升序建大堆//排降序建小堆//先建堆for (int i = (n - 1 - 1)/2; i >=0; i--){AdJustDown(arr, i, n);}//再排序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);//交换堆顶和尾结点AdJustDown(arr, 0, end);end--;}}void test()
{int arr[] = { 6,3,11,9,16,17 };int n = sizeof(arr) / sizeof(arr[0]);//HeapSortUp(arr, n);HeapSortDown(arr, n);for (int i = 0; i < n; ++i){printf("%d ", arr[i]);}}int main()
{test();return 0;
}

在我写的堆排序有两种建堆方法,那哪一种建堆更加高效呢?

来让我们探究它们的复杂度

向上调整算法建堆

由该推算可得向上调整算法建堆的时间复杂度为O(nlogn)

根据图所示可知:

随着结点个数的逐渐增多,结点向上调整的次数也逐渐增多

向下调整算法建堆

由该推算可得向下调整算法建堆的时间复杂度为O(n)

根据图所示可知:

随着结点个数的逐渐增多,结点向下调整的次数也逐渐减少

ss所以在堆排序中最好使用向下调整算法建堆!!!

TOP-K问题

TOP-K问题是指在一堆数据中求前K个最大元素或最小元素,而一般情况下都是在数据量很大的情况下求解的一类问题

题目类型由:专业前10名、世界前500强、游戏中100的活跃玩家等

对于这类型的问题,能想到最简单的解法就是排序,但是在数据量很大的情况下,排序就不能实现不了,因为数据可能无法同时都存储在内存中

最佳的解决方法就是使用堆来解决

思路就是:

1、取N个数据的前K个元素,建堆(求前K个最大元素,建小堆;求前K个最小值,建大堆) 

2、用剩余N-K个元素依次和堆顶元素进行比较,

求前K个最大元素:如果大于堆顶元素就和堆顶元素交换(也就是入堆);

求前K个最小元素:如果大于堆顶元素就和堆顶元素交换(也就是入堆),

然后再将这K个元素进行调整使它们保持为堆

当N-K个元素比完了,堆中剩余的K个元素就是所求的前K个最大元素或最大元素

代码为:

#define _CRT_SECURE_NO_WARNINGS 1
#include"HeapSort.h"void CreateNDate()
{// 造数据int n = 100000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = (rand() + i) % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void TopK()
{int k = 0;printf("请输入K:");scanf("%d", &k);const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");exit(1);}//找最小的前K个数,建大堆int* minHeap = (int*)malloc(sizeof(int) * k);if (minHeap == NULL){perror("malloc fail!");exit(2);}//读取文件中前K个数据建堆for (int i = 0; i < k; i++){fscanf(fout, "%d", &minHeap[i]);}//建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdJustDown(minHeap, i, k);}//遍历剩下的n-k个数据,跟堆顶比较,谁小谁入堆//调整堆int x = 0;while (fscanf(fout, "%d", &x) != EOF){if (x < minHeap[0]){minHeap[0] = x;AdJustDown(minHeap, 0, k);}}for (int i = 0; i < k; i++){printf("%d ", minHeap[i]);}fclose(fout);fout = NULL;
}int main()
{TopK();//CreateNDate();return 0;
}


http://www.ppmy.cn/ops/137443.html

相关文章

微信小程序蓝牙writeBLECharacteristicValue写入数据返回成功后,实际硬件内信息查询未存储?

问题&#xff1a;连接蓝牙后&#xff0c;调用小程序writeBLECharacteristicValue&#xff0c;返回传输数据成功&#xff0c;查询硬件响应发现没有存储进去&#xff1f; 解决&#xff1a;一直以为是这个write方法的问题&#xff0c;找了很多相关贴&#xff0c;后续进行硬件日志…

CSS:怎么把网站都变成灰色

当大家看到全站的内容都变成了灰色&#xff0c;包括按钮、图片等等。这时候我们可能会好奇这是怎么做到的呢&#xff1f; 有人会以为所有的内容都统一换了一个 CSS 样式&#xff0c;图片也全换成灰色的了&#xff0c;按钮等样式也统一换成了灰色样式。但你想想这个成本也太高了…

探索开源多模态视频生成模型:CogVideoX1.5-5B

随着人工智能技术的快速发展&#xff0c;多模态学习逐渐成为研究热点之一。多模态学习旨在通过整合不同类型的感知数据&#xff08;如文本、图像、音频等&#xff09;&#xff0c;以提高机器学习模型的性能和泛化能力。在这一背景下&#xff0c;由智谱AI开发的 CogVideoX1.5-5B…

如何搭建一个小程序:从零开始的详细指南

在当今数字化时代&#xff0c;小程序以其轻便、无需下载安装即可使用的特点&#xff0c;成为了连接用户与服务的重要桥梁。无论是零售、餐饮、教育还是娱乐行业&#xff0c;小程序都展现了巨大的潜力。如果你正考虑搭建一个小程序&#xff0c;本文将为你提供一个从零开始的详细…

c#常见面试题与解析

1.简述 private、 protected、 public、internal 修饰符的访问权限 public 公有的 protected 受保护的 private 私有的 internal 内部的 前三者的关系public>protected>private internal表示在同意程序集内&#xff0c;可访问。 2.列举ASP.NET页面之间传递值的几种…

数据结构(初阶6)---二叉树(遍历——递归的艺术)(详解)

二叉树的遍历与练习 一.二叉树的基本遍历形式1.前序遍历(深度优先遍历)2.中序遍历(深度优先遍历)3.后序遍历(深度优先遍历)4.层序遍历&#xff01;&#xff01;(广度优先遍历) 二.二叉树的leetcode小练习1.判断平衡二叉树1&#xff09;正常解法2&#xff09;优化解法 2.对称二叉…

索尼欲推新一代PSP/PSV掌机,将支持PS4/5游戏

原文转载修改自&#xff08;更多互联网新闻/搞机小知识&#xff09;&#xff1a; 新一代索尼掌机将支持PS4/PS5游戏&#xff0c;或与PS6同时期推出 说起索尼掌机&#xff0c;很难逃得过一句&#xff1a;怒其不争。PSP、PSV打下的大好河山&#xff0c;愣是断送在时代洪流的大浪…

UE5 Spawm Emitter at Location(在位置处生成发射器)

在 Unreal Engine 5 (UE5) 中&#xff0c;Spawn Emitter at Location 是一个非常有用的节点&#xff0c;用来在特定位置生成粒子效果&#xff08;Particle Emitter&#xff09;。这个节点常用于在蓝图中创建临时的粒子效果&#xff0c;例如爆炸、火花或其他动态效果。 如何使用…