做网站能不备案么,做面点的网站,个人网站网页底部模板,wordpress怎么添加会员中心#x1f449;二叉树顺序结构及实现 1.二叉树的顺序结构2.堆的概念及结构3.堆的实现3.1堆向下调整算法3.2堆向上调整算法 4.堆的创建4.1堆创建方法14.1.1构建堆结构体4.1.2堆的初始化4.1.3堆数据添加向上调整4.1.4主函数内容 4.2堆的创建方法24.2.1堆数据添加向下调整 4.3堆数据… 二叉树顺序结构及实现 1.二叉树的顺序结构2.堆的概念及结构3.堆的实现3.1堆向下调整算法3.2堆向上调整算法 4.堆的创建4.1堆创建方法14.1.1构建堆结构体4.1.2堆的初始化4.1.3堆数据添加向上调整4.1.4主函数内容 4.2堆的创建方法24.2.1堆数据添加向下调整 4.3堆数据的删除4.4取根节点的数据4.5回收内存4.6Heap.h头文件展示4. 6Heap.c源文件展示4.7text.c源文件展示 5.堆的用途5.1堆排序5.2 TopK问题 所属专栏初始数据结构❤️ 博主首页初阳785❤️ 代码托管chuyang785❤️ 感谢大家的支持您的点赞和关注是对我最大的支持❤️ 博主也会更加的努力创作出更优质的博文❤️ 关注我关注我关注我重要的事情说三遍❤️ 1.二叉树的顺序结构 普通的二叉树是不适合用数组来存储的因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结 构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分段 简单点解释一下上面的意思就是我们一般用顺序结构来实现完全二叉树而具体是实现方法就是我们把树中的节点都放到一个数组使其看起来是树的结构但是存储方式是以数组的方式存储的。
我们用一张图片来清晰的理解一下。 通过上面的两个图对比只有完全二叉树才可以用顺序表存储也只有这样才能体现出顺序表的特点——连续存储数据
2.堆的概念及结构
说到堆大家可能立马会想起我们操作系统虚拟进程地址空间但是这里我们要讲的是我们二叉树的堆和操作系统虚拟进程地址空间中的堆是两回事我们二叉树中的堆是一种数据结构。 如果有一个关键码的集合K { k0k1 ,k2 …k(n-1) }把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中并满足Ki K(2 * i1) 且 Ki K(2 * i 2) 或者 (Ki K(2 * i1) 且 Ki K(2 * i 2)) i 01 2…则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆根节点最小的堆叫做最小堆或小根堆 堆的性质 堆中某个节点的值总是不大于或不小于其父节点的值 堆总是一棵完全二叉树 用一句话总结就是 大堆就是一颗完全二叉树中的每一个节点的左右孩子都小于等于父节点。 小堆就是一颗完全二叉树中的每一个节点的左右孩子都大于等于父节点。 3.堆的实现
3.1堆向下调整算法
现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整 成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。 int arr[ ] {1, 6, 5, 4, 3, 2 , 1} —— 调整前 int arr[ ] {6, 4, 5, 1, 3, 2 , 1} ——调整后 3.2堆向上调整算法
我们堆的向上调整也是需要左右节点是堆 4.堆的创建
4.1堆创建方法1
4.1.1构建堆结构体
我们现在实现树的方式是顺序表结合我们之前学习的顺序表我们可以很快的想到我们要创建一个结构体结构体包含了arr数组指针用来存放树的数据size用来记录树节点当前的个数capacity用来记录树的容量。
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;4.1.2堆的初始化
初始化就比较简单刚开始我们的树就是为空的。
void HeapInit(HP* php)
{assert(php);php-size php-capacity 0;php-a NULL;
}4.1.3堆数据添加向上调整
我们实现堆的方式是顺序表也就是说我们需要一个数组来存放树所以我们就把数组当作是一颗树来进行。 那么既然数组中存放着数据那我们要怎么把一个乱序的数组给调整为一个堆呢这里我们先使用向上调整算法。 于是我们就想到了我们就把数组中的数据一个一个的放到树中每当放一个进去的时候我们都进向上调整一下这样我们每次进行向调整的时候都满足向上调整的要求左右孩子是堆。
void HeapPush(HP* php, HPDataType x)
{assert(php);//检查容量和顺序表那章节是一样的这里就不多展开讲解了if (php-size php-capacity){int newCapacity php-capacity 0 ? php-capacity 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}else{php-a tmp;php-capacity newCapacity;}}//把数据放到树中php-a[php-size] x;php-size;//向上调整AdjustHeapUp(php-a, php-size - 1);
}而我们知道向上调整的条件是左右孩子是堆这里我们以建大堆为例。只要我们的child大于我们的faster我么就向上调整也就是child和faster进行交换以此类推更新child和faster。
void Swap(int* a, int* b)
{HPDataType tmp *a;*a *b;*b tmp;
}void AdjustHeapUp(HPDataType* a, int child)
{//怎么通过child求parent我们上一章节也见过了不明白的小伙伴可以再去看一看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;}}
}我们来画张图进行深入的剖析。
其实上面的方法可以在优化一下既然是通过一个一个的插入再向上调整的话也就是说是按照数组的下标一次的向上调整那我们不如一步到位直接将数组中的数据memcpy到树中然后从通过一个for循环按照下标 的方式向上调整。
void HeapInitArr(HP* php, int* a, int n)
{assert(php);HPDataType* tmp (HPDataType*)malloc(sizeof(HPDataType) * n);if (tmp NULL){perror(realloc fail);exit(-1);}php-a tmp;memcpy(php-a, a, sizeof(HPDataType) * n);php-size n;php-capacity n;for (int i 1; i n; i ){AdjustHeapUp(php-a, i);}
}4.1.4主函数内容
int main()
{int a[] { 56,89,2,33,6,2,55,6,9,33,8 };HP hp;HeapInit(hp);//建造堆for (int i 0; i sizeof(a)/sizeof(HPDataType); i){HeapPush(hp, a[i]);//通过一个一个插入再向上调整建堆}HeapPrint(hp);HeapDestry(hp);return 0;
}4.2堆的创建方法2
4.2.1堆数据添加向下调整 看到这里的小伙伴有没有发现我们在建堆的时候不仅在栈上开辟了一个数组用来存放要插入树中的数据还在堆区开辟了一块内存表示树但是有没有发现其实这两个地方本质上都是数组那为什么还要开辟堆上的内存呢直接在数组上进行不就行了于是我们就有了向下调整。 我们建堆除了用向上调整还可以用向下调整假想一下我们用向上调整的方法用到向下调整上会是怎么样的。也就是说我们每插入一个数据就向下调整但是这显然是行不通的因为插入一个数据后后面根本就没有数据了何来的向下调整。于是我们不能和向上调整一样一个一个数据的插入而是直接在数组上进行调整。那么问题也来了向下调整也是要求左右孩子是堆才能进行的如果我们从根节点开始的话就不满足条件了所以我们从最后一个节点的度不为0的节点开始向上调整就行了而当我我们调整好了当前节点之后需要调整下一个节点的时候只需要当前节点减减就可以找到另一个需要调整的节点就行了。
void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);//先假设左左孩子int child parent * 2 1;while (child n){//判断是右孩子小还是左孩子小//注意有可能不是满二叉树可能只有左孩子没有右孩子所以要判断child 1 n;if (child 1 n a[child 1] a[child]){child;}//判断parent是否小于孩子if (a[parent] a[child]){Swap(a[parent], a[child]);//更新parentparent child;child parent * 2 1;}else{break;}}
}int main()
{int a[] { 56,89,2,33,6,2,55,6,9,33,8 };HP hp;int len sizeof(a) / sizeof(int);//解释一下len-2/ 2 len是数组的长度但是我们操作的是下标所以说是len - 1//而我们最后一个度不为0的节点的孩子节点肯定是包含了最后一个叶子节点所以显然可以求出最后一个度不为0 的节点就是(len - 1 - 1) / 2for (int i (len - 1 - 1) / 2; i 0; i--){AdjustDown(a, len - 1, i);}for (int i 0; i len; i){printf(%d , a[i]);}return 0;
}如果这里你看明白了相信你也发现了我们的向上调整也是可以这样做的这里就留给小伙伴们自行思考了如果有任何问题都可以在在评论区中提问的哦。
4.3堆数据的删除
⚠️⚠️注这里我们还是使用第一种建堆的方法。
既然我们建好了堆我们要删除堆的数据如果说只是删除堆的最后一个数据那就显得很没有意义所以我们删除堆的数据是删除根节点的数据。设想一下如果我们直接删除根节点的树后因为我们是使用顺序表存放树的数据的直接暴力删除根节点就会破坏我们原先建好的堆结构如果我们还要有堆的结构的话我们就对再次通过建堆的方式重新建堆这无疑是一件大工程。那么有什么好的方法可以做到既删除数据还可以保留堆的结构呢于是我们就想到了可以讲根节点与最后一个叶子节点进行交换然后再删除尾再做一次向下调整就行了。
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size - 1, 0);
}4.4取根节点的数据
HPDataType HeapTop(HP* php)
{assert(php);return php-a[0];
}4.5回收内存
这个讲了很多遍了这里就简单略过。
void HeapDestry(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}4.6Heap.h头文件展示
#pragma once
#include stdio.h
#include stdlib.h
#include assert.h
#include stdbool.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
void AdjustDown(HPDataType* a, int n, int parent);
void AdjustHeapUp(HPDataType* a, int child);
void Swap(int* a, int* b);void HeapPrint(HP* php);
void HeapInit(HP* php);
void HeapInitArr(HP* php, int * a, int n);
void HeapDestry(HP* php);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);4. 6Heap.c源文件展示
#define _CRT_SECURE_NO_WARNINGS 1
#include deap.hvoid HeapInit(HP* php)
{assert(php);php-size php-capacity 0;php-a NULL;
}void HeapInitArr(HP* php, int* a, int n)
{assert(php);HPDataType* tmp (HPDataType*)malloc(sizeof(HPDataType) * n);if (tmp NULL){perror(realloc fail);exit(-1);}php-a tmp;memcpy(php-a, a, sizeof(HPDataType) * n);php-size n;php-capacity n;for (int i 1; i n; i ){AdjustHeapUp(php-a, i);}
}void HeapDestry(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}
void Swap(int* a, int* b)
{HPDataType tmp *a;*a *b;*b tmp;
}void AdjustHeapUp(HPDataType* a, int child)
{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;}}
}void HeapPush(HP* php, HPDataType x)
{assert(php);//检查容量if (php-size php-capacity){int newCapacity php-capacity 0 ? php-capacity 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, sizeof(HPDataType) * newCapacity);if (tmp NULL){perror(realloc fail);exit(-1);}else{php-a tmp;php-capacity newCapacity;}}php-a[php-size] x;php-size;//向上调整AdjustHeapUp(php-a, php-size - 1);
}void HeapPrint(HP* php)
{assert(php);for (int i 0; i php-size; i){printf(%d , php-a[i]);}
}void AdjustDown(HPDataType* a, int n, int parent)
{assert(a);//先假设左左孩子int child parent * 2 1;while (child n){//判断是右孩子小还是左孩子小//注意有可能不是满二叉树可能只有左孩子没有右孩子所以要判断child 1 n;if (child 1 n a[child 1] a[child]){child;}//判断parent是否小于孩子if (a[parent] a[child]){Swap(a[parent], a[child]);//更新parentparent child;child parent * 2 1;}else{break;}}
}void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size - 1, 0);
}HPDataType HeapTop(HP* php)
{assert(php);return php-a[0];
}
4.7text.c源文件展示
int main()
{int a[] { 56,89,2,33,6,2,55,6,9,33,8 };HP hp;HeapInit(hp);//建造堆for (int i 0; i sizeof(a)/sizeof(HPDataType); i){HeapPush(hp, a[i]);}HeapPrint(hp);printf(\n);//这样就可以打印出一个排完序的数据while (!HeapEmpty(hp)){printf(%d , HeapTop(hp));HeapPop(hp);}HeapDestry(hp);return 0;
}5.堆的用途
5.1堆排序
堆的用途之一就是进行堆排序那么如果我们得到一个升序的数组的话我我们应该建大堆还是小堆呢我相信大部分人的第一反应就是建小堆为什么呢因为如果是小堆的话我们就可以找到堆中最小的那个数据然后通过在创建一个数组的方式以及堆Top的方法把最小的放到新建的数组中固然这是一个方法但是不是一个好方法我们能不能就再原数组中进行排序呢答案是可以的这时我们建的是大堆。我们的思路是建好一个大堆后把最后一个叶子节点和根节点进行交换交换后我们的树的节点个数减1然后进行向下调整这个时候我们的数组中最大的数到了最后一个并且向下调整的时候不参与调整以此类推知道数的节点个数为0为止我们就排好序了。
void sort(int* a, int n)
{//把数组直接看成是一个对然后对其进行向上调整得到大堆//升序建大堆降序建小堆int i 0;for (int i 1; i n; i){AdjustHeapUp(a, i);}int end n - 1;while (end 0){Swap(a[0], a[end]);//向下调整AdjustDown(a, end, 0);end--;}
}int main()
{int a[] { 56,89,2,33,6,2,55,6,9,33,8 };sort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i){printf(%d , a[i]);}
}相反的如果要弄降序就建小堆。
5.2 TopK问题 所谓TopK就是取出前K个最大的数或者后K个最小的数。 这里就那取出前K个最大的数来举例子而且是以文件的形式进行存储。 假如有n个数据找出前k个最大的数据。 我们的方法就是 1️⃣ .先创建一个节点个数为K的小堆 2️⃣ .一次遍历n-k个数据 3️⃣ .每次遍历后都与根节点比较如果大于根节点就是根节点等于该数据再进行向下调整
#define _CRT_SECURE_NO_WARNINGS 1
#include stdio.h
#include string.h
#include time.h
#include stdlib.h//HeapTopK问题找出数据中前k个大的数据
//步骤
// 1.先创建k个节点的堆如果是找前k的大的数据就建小堆如果是找前k个小的就建大堆
// 2.然后用剩下的数据和堆的根比较如果比根大就替换然后向下调整
// 3.遍历完毕后堆中的数据就是想要的结果了。const int N 10000;void CreatData()
{//设置随机种子srand((unsigned int)time(NULL));const char* file_name data.txt;//将数据写到文件中FILE* file fopen(file_name, w);if (file NULL){perror(fopen file);return;}for (int i 0; i N; i){int x rand() % 1000000;fprintf(file, %d\n, x);}fclose(file);
}void Swap(int* a, int* b)
{int tmp *a;*a *b;*b tmp;
}void AdjustDown(int* a, int k ,int parent)
{int child parent * 2 1;while (child k){if (child 1 k a[child 1] a[child]){child;}if (a[parent] a[child]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}void print_topK(int k)
{int arr1[10000];//首先把文件中的前k个数据放到堆中创建小堆FILE* file fopen(data.txt, r);//创建存放堆的顺序表int* arr2 (int*)malloc(sizeof(int) * k);if (arr2 NULL){perror(malloc);return;}for (int i 0; i N; i){int x 0;fscanf(file, %d, x);arr1[i] x;}//把前k个数据放到arr中for (int i 0; i k; i){arr2[i] arr1[i];}//向下调整形成小堆for (int i (k - 2) / 2; i 0; i--){AdjustDown(arr2,k, i);}//遍历剩下的数据for (int i k; i N; i){if (arr2[0] arr1[i]){arr2[0] arr1[i];AdjustDown(arr2, k, 0);}}for (int i 0; i k; i){printf(%d , arr2[i]);}fclose(file);
}int main()
{int k 10;//创建10000个数据放到文件中//CreatData();print_topK(10);
}
