欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 新闻 > 社会 > 【数据结构】堆的实现

【数据结构】堆的实现

2024/11/8 7:32:12 来源:https://blog.csdn.net/2302_81312180/article/details/143417759  浏览:    关键词:【数据结构】堆的实现

目录

1. 堆向上调整算法

1.1 时间复杂度​编辑

2. 堆向下调整算法

2.1 时间复杂度

3. 建堆算法

 3.1 向上调整建堆

3.2 向下调整建堆

4. 建堆算法的时间复杂度

5. 关于堆排序建大小堆问题

6. 堆排序

6.1 堆排序的时间复杂度

7.Top_k问题

8. 实现堆

8.1 初始化堆

8.2 销毁堆

8.3 堆的插入

8.4 堆的删除

8.5 获取堆顶数据

8.6 获取堆的数据个数

8.7 堆的判空

9. 总结

Heap.c

Heap.h


1. 堆向上调整算法

基本思想:

向堆尾插入新元素时,维护堆的性质,需要对该元素向上调整,从新插入的节点开始,与其父节点比较,若新节点的值比其父节点的值小,则交换它们,并将新节点的父节点当作目标节点继续向上调整,若目标结点的值比其父结点的值大,就停止向上调整,此时该树已成堆。 (以小堆调整为例)

代码实现: 

//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向上调整(小堆)
void AdjustUp(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;}}
}

1.1 时间复杂度

向上调整算法,插入一个节点,最多走log₂N次,时间复杂度为O(logN)

2. 堆向下调整算法

现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。

向下调整算法有一个前提

若想将此二叉树调整为小堆,左右子树都必须是一个小堆,才能调整。

若想将此二叉树调整为大堆,左右子树都必须是一个大堆,才能调整。

代码实现: 

//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整(小堆)
void AdjustDown(HPDataType* a, int n,int parent)
{//先假设左孩子小(假设法)int child = parent * 2 + 1;//先默认其左孩子的值较小while (child < n)   //child>=n说明孩子不存在,已经调整到叶子节点了{//找出小的那个孩子if (child+1<n && a[child + 1] < a[child])//如果右孩子的值小于左孩子  兼容一下最后面只有左孩子的情况防止child+1越界{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//继续向下调整parent = child;child = parent * 2 + 1;}else//已成堆{break;}}
}

2.1 时间复杂度

向下调整算法,从根节点开始向下调整,最多走高度(log₂N)次 ,时间复杂度为O(logN)

3. 建堆算法

 3.1 向上调整建堆

代码实现: 

void HeapSort(int* p, int n)
{//向上调整建堆 时间复杂度O(N*logN)for (int i = 1; i < n; i++){		AdjustUp(p, i);  //降序(建小堆);升序(建大堆) //直接传数组的地址,把它当成一个堆		}
}
int main()
{	int p[] = { 4,2,8,1,5,6,9,7 };HeapSort(p, sizeof(p) / sizeof(p[0]));return 0;
}

由于使用堆的向下调整算法有一个前提,要求左右子树均为大堆或小堆,那么对于任意树,如何把它调整成堆呢?

倒数第一个非叶子结点开始,从后向前调整,一直调整到根结点就成堆了。

3.2 向下调整建堆

代码实现:

void HeapSort(int* p, int n)
{//向下调整建堆    时间复杂度为O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--) //从倒数第一个非叶子节点开始向下调整{     AdjustDown(p, n, i);}	
}int main()
{	int p[] = { 4,2,8,1,5,6,9,7 };HeapSort(p, sizeof(p) / sizeof(p[0]));return 0;
}

4. 建堆算法的时间复杂度

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简便使用满二叉树来证明(看近似值,多几个结点不影响最终结果):

我们很容易认为向下调整建堆的时间复杂度是O(N)=(n - 1 - 1) / 2*logN=N*logN,接下来推理一下:

    //向下调整建堆  for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(p, n, i);}

总结:向下调整建堆的时间复杂度为O(N) 

总结:向上调整建堆的时间复杂度为O(N*logN) 

所以我们发现向下调整建堆比向上调整建堆时间复杂度更优,当进行堆排序时,建堆的时候需要向下调整,排序的时候需要向下调整,这样只需要封装一个向下调整函数就可以了。

5. 关于堆排序建大小堆问题

思考一下:当要让一组数据降序排列时,我们建大堆还是小堆呢?

通常我们会建大堆,其实如果建大堆,第一个数据是最大的,它已经被排好了,再要从剩下的数据中选出次大的,再把剩下的数据看作一个堆,此时数据间的关系全部混乱,需要重新建堆,但是代价太大了。正确的做法是建小堆,让首尾数据交换,尾数据即最小的数,再进行向下调整,调整到第一个数据是次小的。

  • 堆排序若排升序,则要建大堆
  • 堆排序若排降序,则要建小堆 

6. 堆排序

基本思想

把无序数组使用向下调整建堆算法构建成堆,首尾元素交换,堆顶最小的元素被替换到最后面,再向下调整,第二小的元素会成为堆顶元素,每次调整的范围都减少一个即排除掉最后一个元素,反复交换,反复调节,直到堆的大小变成1。

代码实现:

#include<stdio.h>//交换函数
void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整(建小堆)
void AdjustDown(int* a, int n,int parent)
{//先假设左孩子小(假设法)int child = parent * 2 + 1;//先默认其左孩子的值较小while (child < n)   {//找出小的那个孩子if (child+1<n && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//继续向下调整parent = child;child = parent * 2 + 1;}else//已成堆{break;}}
}//堆排序(排降序)  
void HeapSort(int* p, int n)
{//向下调整建堆  时间复杂度为O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--)//从倒数第一个非叶子节点开始向下调整{AdjustDown(p, n, i);}//时间复杂度为O(N*logN)   int end = n - 1;  //n-1为堆最后一个数据的下标while (end > 0){Swap(&p[0], &p[end]);//首尾交换AdjustDown(p, end, 0);//向下调整  需调整的数据个数为end个--end;}
}int main()
{	int p[] = { 4,2,8,1,5,6,9,7 };HeapSort(p, sizeof(p) / sizeof(p[0]));for (int i = 0; i < sizeof(p) / sizeof(p[0]); i++){printf("%d ", p[i]);}printf("\n");return 0;
}

运行结果:

6.1 堆排序的时间复杂度

我们已知向下调整建堆的时间复杂度为O(N),在排序的过程中,每次要选出剩余数中的最大的树,再进行向下调整,总共需要执行N次,而向下调整算法的时间复杂度为O(logN),进行N次即O(N*logN),整个过程的时间复杂度为O(N+N*logN)即为O(N*logN)

7.Top_k问题

问题描述:

从arr[1, n]这n个数中,找出最大的k个数,这就是经典的TopK问题。

在生活中有很多涉及top-k问题,比如世界五百强,学校专业前几名,富豪榜等等。对于TOP-K问题,可能第一反应是用排序,将前几名排序出来,但当数据量很大很大时,排序就不好处理了,数据不能一下完全加载到内存中去。而解决这样的问题,最好的方式是用堆来处理。

基本思想:

先用前k个元素生成一个小堆,这个小堆用于存储当前最大的k个元素,接着,从k+1个元素开始扫描,如果扫描到的元素比堆顶数据大,就替换掉它,并进行向下调整,保证堆内的数据总是当前最大的k个数。得到的Top-k是未排序的。

时间复杂度:O(k)+O((N-k)*logk)=O(N*logk),这里就不合并了。

其实通过复杂度可以看出,这样做效率并没有太大的提升,但是空间消耗极少。

  • 找前k个最大的元素,就建小堆。
  • 找前k个最小的元素,就建大堆。

代码实现:

#define _CRT_SECURE_NO_WARNINGS 1
#include<time.h>
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int HPDataType;
//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{//先假设左孩子小(假设法)int child = parent * 2 + 1;while (child < n)   {//找出小的那个孩子if (child + 1 < n && a[child + 1] < a[child]){child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//继续向下调整parent = child;child = parent * 2 + 1;}else//已成堆{break;}}
}//造数据
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) % 100000;//造出来的数比100000小fprintf(fin, "%d\n", x);}fclose(fin);
}void TestHeap()
{int k;printf("请输入k:  ");scanf("%d", &k);int* kminheap = (int*)malloc(sizeof(int) * k);if (kminheap == NULL){perror("malloc fail");return;}const char* file = "data,txt";FILE* pf = fopen(file, "r");if (pf == NULL){perror("fopen error");return;}//读取文件中前k个数for (int i = 0; i < k; i++){fscanf(pf,"%d", &kminheap[i]);}//建k个数的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--)//倒数第一个非叶子节点{AdjustDown(kminheap, k, i);}//读取剩下的N-K个数int x = 0;while (fscanf(pf,"%d", &x)>0 ){if (x > kminheap[0]) //如果读取到的值比堆顶数据大{kminheap[0] = x; //替换堆顶数据AdjustDown(kminheap, k, 0);}}printf("最大前%d个数:", k);for (int i = 0; i < k; i++){printf("%d ", kminheap[i]);}printf("\n");}int main()
{		//CreateNDate();TestHeap();return 0;
}

我们造了十万个数据,要找最大的前k个,我们怎么验证得到的数据是不是最大的前k个呢?

把找数据函数代码屏蔽掉造数据,再把造数据代码屏蔽掉,去往装数据的文件里随机改动数据,运行找数据函数,就会发现我们改动的数据被找了出来,因为其它数据都比100000小,我们改动的数据比100000大,比较显眼,以此来判断我们的代码是否有问题。

运行结果:

8. 实现堆

8.1 初始化堆

创建一个堆类型

typedef int HPDataType;//堆中存储数据的类型
typedef struct Heap
{HPDataType* a; //用于存储数据的数组int size;      //记录堆中已有的元素个数int capacity;  //堆的容量
}HP;
//初始化堆
void HPInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}

8.2 销毁堆

为了避免内存泄漏,动态开辟的内存空间使用完之后后要及时释放。

//销毁堆
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}

8.3 堆的插入

插入数据到数组的末尾,即树形结构的最后一个结点,插入完数据之后我们需要进行向上调整,使其在插入数据后仍然保持堆的结构。

//堆的插入
void HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);//向上调整
}

8.4 堆的删除

删除堆是删除堆顶的数据,将堆顶的数据根和最后一个数据交换,然后删除数组最后一个数据,再进行向下调整算法。

删除堆堆顶数据,不能挪动覆盖删除,不然关系就全部混乱了,我们把堆顶数据和最后一个数据交换,再删除最后一个数据,然后进行向下调整,调整完后堆顶数据依然是最小的,相较于删除的那个数据是次小的。所以在日常应用中,当数据量很多的时候,想要找较大或较小的几个数据,直接pop几次就可以了。

//堆的删除
void HPPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;//删除堆中最后一个元素AdjustDown(php->a, php->size, 0);
}

8.5 获取堆顶数据

//获取堆顶数据
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

8.6 获取堆的数据个数

//获取堆的数据个数
int HPSize(HP* php)
{assert(php);return php->size;
}

8.7 堆的判空

//堆的判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

9. 总结

Heap.c

#include"Heap.h"//初始化堆
void HPInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}//销毁堆
void HPDestroy(HP* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp = *p1;*p1 = *p2;*p2 = tmp;
}//向上调整
void AdjustUp(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 HPPush(HP* php, HPDataType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);//向上调整
}//向下调整
void AdjustDown(HPDataType* a, int n,int parent)
{//先假设左孩子小(假设法)int child = parent * 2 + 1;//先默认其左孩子的值较小while (child < n)   //child>=n说明孩子不存在,已经调整到叶子节点了{//找出小的那个孩子if (child+1<n && a[child + 1] < a[child])//如果右孩子的值小于左孩子  兼容一下最后面只有左孩子的情况防止child+1越界{child++;}if (a[child] < a[parent]){Swap(&a[child], &a[parent]);//继续向下调整parent = child;child = parent * 2 + 1;}else//已成堆{break;}}
}//堆的删除
void HPPop(HP* php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;//删除堆中最后一个元素AdjustDown(php->a, php->size, 0);
}//获取堆顶数据
HPDataType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}//获取堆的数据个数
int HPSize(HP* php)
{assert(php);return php->size;
}//堆的判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

Heap.h

#define _CRT_SECURE_NO_WARNINGS 1#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//交换函数
void Swap(HPDataType* p1, HPDataType* p2);
//向上调整
void AdjustUp(HPDataType* a, int child);
//向下调整
void AdjustDown(HPDataType* a, int n, int parent);
//初始化堆
void HPInit(HP* php);
//销毁堆
void HPDestroy(HP* php);
//堆的插入
void HPPush(HP* php, HPDataType x);
//堆的删除
void HPPop(HP* php);
//获取堆顶数据
HPDataType HPTop(HP* php);
//获取堆的数据个数
int HPSize(HP* php);
//堆的判空
bool HPEmpty(HP* php);

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com