嘉兴网站建设成都网站设计,常用网站设计缩略图,全国工商企业信息查询网,大连网站制作诚推ls15227创作不易#xff0c;兄弟们给个三连#xff01;#xff01;
一、二叉树的顺序存储 顺序结构指的是利用数组来存储#xff0c;一般只适用于表示完全二叉树#xff0c;原因如上图#xff0c;存储不完全二叉树会造成空间上的浪费#xff0c;有的人又会问#xff0c;为什么… 创作不易兄弟们给个三连
一、二叉树的顺序存储 顺序结构指的是利用数组来存储一般只适用于表示完全二叉树原因如上图存储不完全二叉树会造成空间上的浪费有的人又会问为什么图中空的位置不能存储呢原因是我们需要根据数组的下标关系才能访问到对应的节点有以下两个下标关系公式
1、父亲找孩子leftchildparent*21rightchildparent*22
2、孩子找父亲parentchild-1/2 要注意这边无论用左孩子算还是右孩子算都是可以的因为一般俩说child-1/2 由于int类型向下取整的特点所以得到的结果都是一样的 所以我们想要上面这种方式去访问节点并且还不希望有大量的空间浪费现实中只有堆才会使用数组存储二叉树的顺序存储中在物理上是一个数组再逻辑上是一颗二叉树
二、堆的概念及结构 现实中我们把堆类似完全二叉树使用顺序结构来存储要注意这里的堆和操作系统虚拟进程地址空间中的堆是两回事一个是数据结构一个是操作系统中管理内存的一块区域分区。 如果有一个关键码的集合k我们将他的全部元素按照完全二叉树的存储逻辑放在一个一维数组中则成为堆根节点最大的堆叫做大堆根节点最小的堆叫做小堆。
堆的性质
1、堆中某个节点的值总是不大于或不小于其父节点的值
2、堆总是一颗完全二叉树 注意并不一定有序
三、堆的实现
假设我们实现小堆
3.1 相关结构体的创建
跟顺序表的形式是一样的但是换了个名字
typedef int HPDataType;
typedef struct Heap
{HPDataType * a;int size;int capacity;
}Heap;
3.2 堆的初始化
void HeapInit(Heap* php)
{assert(php);php-a NULL;php-capacity php-size 0;
}
3.3 堆的插入
堆的插入很简单但是我们要保证堆插入后还能维持堆的形状 所以我们在插入后还要进行向上调整也就是孩子要根据下标关系找到自己的父亲去比较小就交换
void HeapPush(Heap* php, HPDataType x)
{assert(php);//首先要判断是否需要扩容if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDataType* temp (HPDataType*)realloc(php-a,sizeof(HPDataType) * newcapacity);if (temp NULL){perror(malloc fail);exit(1);}//扩容成功php-a temp;php-capacity newcapacity;}//扩容后我们插入这个元素并sizephp-a[php-size] x;//但是插入之后可能会破坏堆的结构所以我们需要这个元素和他的父辈进行逐个比较 AdjustUp(php-a,php-size-1);//封装一个向上调整函数传入数组和新加元素的下标
}
3.4 向上调整算法
void AdjustUp(HPDataType* a, int child)
{assert(a);//通过孩子找父亲 parent(child-1)/2int parent (child - 1) / 2;//孩子和父亲开始比较如果孩子小就交换如果孩子大退出循环while (child0)//如果孩子变成了根节点就没有必要再找了因为已经没有父母了//如果用parent0来判断那么由于0-1/2是-1/2取整后还是0就会一直死循环所以必须用孩子来当循环条件{if (a[child] a[parent])//孩子小交换{Swap(a[child], a[parent]);//但是交换过后可能还需要继续往上比所以我们要让原来的父亲变成孩子然后再找新的父亲进行比较child parent;parent (child - 1) / 2;}else//孩子大退出break;}
}
注这里的向上调整算法和后面向下调整算法我们都不用跟堆有关的接口原因就是这个算法的运用范围很广可以用在堆排序以及top-k问题中
3.5 交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType temp *p1;*p1 *p2;*p2 temp;
}
3.6 堆的删除 一般来说如果直接删除堆的最后一个元素其实是没什么意义的一行代码就可以搞定没必要封装什么函数所以这里的堆的删除指的是删除根部的元素 void HeapPop(Heap* php)//一般来说堆中的删除指的是删除根位置的数据
//如果直接删除根然后往前挪动一位那么亲缘关系就会十分混乱为了能够尽量在调整中减少对关系的改变
//我们将根部元素与最后一个元素进行交换之后再删除此时的根是原先的最后一个元素
//然后将该元素进行向下调整封装一个函数传入数组、元素个数、
{assert(php);assert(!HeapEmpty(php));//为空的话没有删除的必要Swap(php-a[0], php-a[php-size - 1]);php-size--;//开始向下调整AdjustDown(php-a, php-size,0);
}
3.7 向下调整算法
void AdjustDown(HPDataType* a, int n,int parent)
{assert(a);//此时根部为原来的最后一个元素,往下比较//即通过父亲去找到自己的孩子如果孩子比自己小就得交换位置如果孩子比自己大就退出//但是因为父亲有一个左孩子parent*21右孩子parent*22我们选择孩子中较小的和自己交换int child parent * 2 1;//假设左孩子比右孩子小while (childn)//当child超出个数的时候结束{if (child1n a[child 1]a[child])//如果右孩子比左孩子小假设错误修正错误//注意一定不能写反要注意只有左孩子没有右孩子的情况child;if (a[child] a[parent])//如果孩子小于父亲交换{Swap(a[child], a[parent]);//交换完后让原来的孩子变成父亲然后再找新的孩子parent child;child parent * 2 1;}elsebreak;//如果孩子大于等于父亲直接退出}
} 在上述算法中我们应用了先假设再推翻的方法一开始我们先假设左孩子比较小然后我们再给个条件判断如果左孩子大于右孩子假设不成立再推翻这样可以保证我们的child变量一定是较小的孩子 虽然这里的parent很明显是从a[0]开始好像不需要专门去传一个parent的参数但是这也是为了之后的堆排序做准备
3.8 取堆顶的数据
HPDataType HeapTop(Heap* php)
{assert(php);assert(!HeapEmpty(php));//为空的话没有取的必要return php-a[0];
}
3.9 堆的数据个数
int HeapSize(Heap* php)
{assert(php);return php-size;
}3.10 堆的判空
bool HeapEmpty(Heap* php)
{assert(php);return php-size 0;
}
3.11 堆的销毁
void HeapDestory(Heap* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}
3.12 堆的打印测试
我们要实现堆的打印利用我们之前封装的函数每获取一次堆顶元素就删除一次直到堆删完就可以获取全部的元素了
#includeHeap.h
int main()//该方法实现堆的顺序打印
{Heap hp;HeapInit(hp);int a[] { 55,100,70,32,50,60 };for (int i 0; i sizeof(a) / sizeof(int); i)HeapPush(hp, a[i]);//不断进堆while (!HeapEmpty(hp)){int top HeapTop(hp);printf(%d\n, top);HeapPop(hp);}HeapDestory(hp);return 0;
}
前面只是先创建一个堆从while循环开始才是实现对堆的打印 运行结果 32 50 55 60 70 100 我们发现了一个情况按道理来说堆只有父子节点之间有大小关系兄弟之间没有的但是我们最后打印出来的结果却完成了排序下面我们来进行分析 总之任何一个堆我们都可以通过不断地pop去实现它的顺序打印堆排序后面会介绍
四、堆实现的全部代码
4.1 Heap.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.htypedef int HPDataType;
typedef struct Heap
{HPDataType * a;int size;int capacity;
}Heap;void Swap(HPDataType* p1, HPDataType* p2);//实现父亲和孩子的交换
void AdjustUp(HPDataType* a, int child);//向上调整算法// 堆的初始化
void HeapInit(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
int HeapSize(Heap* php);
// 堆的判空
bool HeapEmpty(Heap* php);
// 堆的销毁
void HeapDestory(Heap* php);4.2 Heap.c
#includeHeap.h
//当前实现小堆
void HeapInit(Heap* php)
{assert(php);php-a NULL;php-capacity php-size 0;
}void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType temp *p1;*p1 *p2;*p2 temp;
}void AdjustUp(HPDataType* a, int child)
{assert(a);//通过孩子找父亲 parent(child-1)/2int parent (child - 1) / 2;//孩子和父亲开始比较如果孩子小就交换如果孩子大退出循环while (child0)//如果孩子变成了根节点就没有必要再找了因为已经没有父母了//如果用parent0来判断那么由于0-1/2是-1/2取整后还是0就会一直死循环所以必须用孩子来当循环条件{if (a[child] a[parent])//孩子小交换{Swap(a[child], a[parent]);//但是交换过后可能还需要继续往上比所以我们要让原来的父亲变成孩子然后再找新的父亲进行比较child parent;parent (child - 1) / 2;}else//孩子大退出break;}
}void AdjustDown(HPDataType* a, int n,int parent)
{assert(a);//此时根部为原来的最后一个元素,往下比较//即通过父亲去找到自己的孩子如果孩子比自己小就得交换位置如果孩子比自己大就退出//但是因为父亲有一个左孩子parent*21右孩子parent*22我们选择孩子中较小的和自己交换int child parent * 2 1;//假设左孩子比右孩子小while (childn)//当child超出个数的时候结束{if (child1n a[child 1]a[child])//如果右孩子比左孩子小假设错误修正错误//注意一定不能写反要注意只有左孩子没有右孩子的情况child;if (a[child] a[parent])//如果孩子小于父亲交换{Swap(a[child], a[parent]);//交换完后让原来的孩子变成父亲然后再找新的孩子parent child;child parent * 2 1;}elsebreak;//如果孩子大于等于父亲直接退出}
}void HeapPush(Heap* php, HPDataType x)
{assert(php);//首先要判断是否需要扩容if (php-size php-capacity){int newcapacity php-capacity 0 ? 4 : 2 * php-capacity;HPDataType* temp (HPDataType*)realloc(php-a,sizeof(HPDataType) * newcapacity);if (temp NULL){perror(malloc fail);exit(1);}//扩容成功php-a temp;php-capacity newcapacity;}//扩容后我们插入这个元素并sizephp-a[php-size] x;//但是插入之后可能会破坏堆的结构所以我们需要这个元素和他的父辈进行逐个比较 AdjustUp(php-a,php-size-1);//封装一个向上调整函数传入数组和新加元素的下标
}void HeapPop(Heap* php)//一般来说堆中的删除指的是删除根位置的数据
//如果直接删除根然后往前挪动一位那么亲缘关系就会十分混乱为了能够尽量在调整中减少对关系的改变
//我们将根部元素与最后一个元素进行交换之后再删除此时的根是原先的最后一个元素
//然后将该元素进行向下调整封装一个函数传入数组、元素个数、
{assert(php);assert(!HeapEmpty(php));//为空的话没有删除的必要Swap(php-a[0], php-a[php-size - 1]);php-size--;//开始向下调整AdjustDown(php-a, php-size,0);
}HPDataType HeapTop(Heap* php)
{assert(php);assert(!HeapEmpty(php));//为空的话没有取的必要return php-a[0];
}int HeapSize(Heap* php)
{assert(php);return php-size;
}bool HeapEmpty(Heap* php)
{assert(php);return php-size 0;
}void HeapDestory(Heap* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}
4.3 test.c测试
#includeHeap.h
int main()//该方法实现堆的顺序打印
{Heap hp;HeapInit(hp);int a[] { 55,100,70,32,50,60 };for (int i 0; i sizeof(a) / sizeof(int); i)HeapPush(hp, a[i]);//不断进堆while (!HeapEmpty(hp)){int top HeapTop(hp);printf(%d\n, top);HeapPop(hp);}HeapDestory(hp);return 0;
}五、堆的应用
5.1 堆排序
要对数组排序前我们要用堆排序首先要建堆
大家看看之前堆的打印时的测试代码逻辑的方法
就是我们得到一个数组就先建堆然后先把数组push进去再pop出来是可以实现有序的 但是现在我们的需求不是打印出来而是将他排好序后放进数组里所以们可以这么写
void HeapSort(int* a, int n)
{HP hp;HeapInit(hp);// N*logNfor (int i 0; i n; i){HeapPush(hp, a[i]);}// N*logNint i 0;while (!HeapEmpty(hp)){int top HeapTop(hp);a[i] top;HeapPop(hp);}HeapDestroy(hp);
} 这个方法固然是可以的但是很麻烦原因如下
1、每次都要建立一个新的堆然后再销毁比较麻烦而且空间复杂度比较高
2、我通过把数组放进变成堆还要再把堆拷贝到数组中数据的拷贝是很繁琐的
所以我们要思考一种方式避免数据的拷贝所以就有了向上调整建堆和向下调整建堆的方法了
也就是我们在原数组的基础上直接建堆然后向下调整排序即可下面会详细介绍
5.1.1 向上调整建堆 假设数组有n个元素
for (int i 1; i n; i)
{AdjustUp(a, i);
}
5.1.2 向下调整建堆 for (int i (n-1-1)/2; i 0; i--)
{AdjustDown(a, n, i);
}
5.1.3 堆排序的实现
那我们究竟选择向下建堆好还是向下建堆好呢我们来分析一下 所以我们发现向上调整建堆的时间复杂度大概是N*logN而向下调整建堆的时间复杂度是N
其实们在推导的时候也能发现向上调整建堆是节点多的情况调整得多节点少的情况调整的少次数是多*多少*少 而向下调整建堆是节点多的情况调整得少节点少的情况调整的多次数是多*少少*多显然是向下调整建堆是更有优势的 接下去我们建好堆就要想着怎么去排序了我们思考一下之前我们对堆的打印时不断pop打印出来有序结果的原因是什么原因就是pop函数里的向下调整算法每一次交换根节点和尾节点将每个节点进行向下调整最后就可以得到有序的 因为我们之前实现的向下调整算法是小堆的所以我们这边来实现一个降序的堆排序算法
void HeapSort(int* a, int n)
{//降序 建小堆//升序 建大堆for (int i (n-1-1)/2; i 0;i--)AdjustDown(a, n, i);//开始排序 先交换向下调整int end n - 1;while (end 0){Swap(a[0], a[end]);AdjustDown(a, end, 0);--end;}
} 如果我们想实现升序将向下调整算法按照大堆的规则改一下就行
向下调整算法和向上调整算法的空间复杂度都是logN
堆排序中建堆的时间复杂度是oN排序的时间复杂度是N*logN所以堆排序的总时间复杂度是N*logN
5.2 TOP-K问题
Top-k问题即求数据中前k个最大的元素或者是最小的元素一般情况下的数据量都比较大
比如专业前10名、世界五百强、富豪榜前十
堆排序能够帮助我们在大量数据中筛选出最好的几个。
5.2.1 思路 比如说我们要从1000个学生的成绩中找到前10个分数最高的方法就是将所有的数据放在一个数组里直接建大堆然后pop9次就可以找到了pop中的向下调整算法可以使得每次pop出去的都是最大值然后pop9次的原因是因为第10次就可以直接去获取堆顶元素即可 但是有些情况上述思路解决不了分析 5.2.2 通过数组验证TOP-K
void PrintTopK(int* a, int n, int k)
{//建前k个建小堆for (int i (k - 1 - 1) / 2; i 0; i--)AdjustDown(a, k, i);//将剩余n个数据不断与堆顶元素比较大就交换,然后向下调整for (int i k; i n; i){if (a[i] a[0]){a[0] a[i];//直接覆盖就行不用交换AdjustDown(a, k, 0);}}//打印for(int i0;ik;i)printf(%d , a[i]);
}void TestTopk()
{int n 10000;int* a (int*)malloc(sizeof(int) * n);srand((unsigned int)time(NULL));for (size_t i 0; i n; i){a[i] rand() % 1000000;//随机数范围0-999999}
// 为了能够方便找到这些数a[5] 1000000 1;a[1231] 1000000 2;a[531] 1000000 3;a[5121] 1000000 4;a[115] 1000000 5;a[2335] 1000000 6;a[9999] 1000000 7;a[76] 1000000 8;a[423] 1000000 9;a[3144] 1000000 10;PrintTopK(a, n, 10);
}int main()
{TestTopk();return 0;
}5.2.3 通过文件验证TOP-K
其实用数组的方法并不能有效地模拟我们可以尝试用文件的方式来验证
void CreateNDate()
{// 造数据int n 10000;srand((unsigned int)time(NULL));const char* file data.txt;FILE* fin fopen(file, w);if (fin NULL){perror(fopen error);return;}for (size_t i 0; i n; i){int x rand() % 1000000;fprintf(fin, %d\n, x);//将随机数写进文件}fclose(fin);
}void PrintTopK(int k)
{const char* file data.txt;FILE* fout fopen(file, r);if (fout NULL){perror(fopen fail);return;}int* kminheap (int*)malloc(sizeof(int) * k);if (kminheap NULL){perror(malloc fail);return;}for (int i 0; i k; i){fscanf(fout, %d, kminheap[i]);//从文件读取数据}// 建小堆for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDown(kminheap, k, i);}int val 0;while (!feof(fout))//feof是文件结束的标识如果返回1则说明文件结束{fscanf(fout, %d, val);//fscaf的光标闪动到原先的位置所以会从k的位置开始读if (val kminheap[0]){kminheap[0] val;AdjustDown(kminheap, k, 0);}}for (int i 0; i k; i){printf(%d , kminheap[i]);}printf(\n);
}
int main()//该方法实现堆的顺序打印
{CreateNDate();PrintTopK(5);return 0;
}
友友们上述代码有不理解的看看博主关于文件操作里的函数介绍
C语言文件操作详解-CSDN博客 不太好找所以我们可以先注释创造数据的文件然后再文件中修该出5个最大数然后再执行一次函数 以上就是通过数组验证top和利用文件验证tok的方法
