文章目录希望这篇文章对你有益,如果你发现哪里有问题,希望您能不吝赐教。
- 前言
- 一、数据结构的堆是什么
- 二、逻辑结构的堆
- 三、建堆
- 四、堆排序
- 五、TopK问题
- 六、总结
前言
例如:堆的逻辑结构是完全二叉树,看后面的知识需要你有一点点二叉树的概念,你需要知道父子结点,二叉树的结构,以及顺序表的基本知识!
一、数据结构的堆是什么?
数据结构的堆物理结构是数组,逻辑结构是完全二叉树(这里可以联想链表的物理、逻辑结构的不同),这里引入一个问题就是:如何让数组变成二叉树,也就是说一个数据如何与另外两个数据产生联系?带着这个问题,我们往下看。
二、逻辑结构的堆
给一个数组{9,7,2,6,3,5,1,4,8},他的逻辑结构:
0->1、0->2、1->3、1->4 反过来列举我们可以通过下标找到数据查找关系
把9当作parent,把7,2当作child1和child2,那么我们总结可知 : child1=parent*2+1; child2=parent*2+2; parent=(child-1)/2;由这两个不同角度的重要结论,我们可以由此实现物理->逻辑的联系,下面来实现建堆!
三、建堆
堆分为小堆和大堆,小堆是所有的双亲结点要小于自己的字结点,大堆就是双亲结点要大于自己的子节点。建堆就是将堆建成小堆或者大堆。
下面上代码教你如何建堆~
1.堆的基本框架(顺序表)
typedef int HeapDataType; typedef struct Heap { HeapDataType* a; int size; int capacity; }Heap;
2.堆的初始化
void HeapInit(Heap* php) { php->a = (HeapDataType*)malloc(sizeof(HeapDataType) * 8); php->capacity = 8; php->size = 0; }3.建堆(以大堆为例)
Way1:向上调整法
//向上排序法(孩子找父亲) 时间复杂度0(N*logN) void AdjustUp(HeapDataType* a, int child) { //1.找父亲 int parent = (child - 1) / 2; while (child > 0) { //2.比较父子结点 if (a[child] > a[parent]) { //交换 swap(&a[child], &a[parent]); //迭代 child = parent; parent = (child - 1) / 2; } else { break; } } } //建堆 void HeapCreate(Heap* php, HeapDataType* a, int size) { for (int i = 0;i < size;i++) { HeapPush(php, a[i]); } }
方法:通过子节点找到父结点,比较父与子结点大小,子节点大于父结点那么就交换,否则不交换。不交换说明这对父子结点已满足大堆条件,不需要动它们;交换则迭代执行下一次比较!
计算时间复杂度:
Way2:向下调整法(大堆为例)
思路:从第一个非叶结点开始,从子结点中找出最大的结点,比较父子结点的大小,如果子结点大于父节点则交换,然后迭代,否则说明已满足大堆条件,直接结束调整。
//利用向下调整法建大堆 时间复杂度0(N) int arr[] = { 9,7,2,6,3,5,1,4,8 }; //这里i起始应该是第一个非叶子结点 最后一个结点时n-1,parent=(n-1-1)/2 for (int i = (n-2)/2;i>=0;i--) { AdjustDown(a, n, i); } void AdjustDown(HeapDataType* a, int size,int parent) { 1.父亲找孩子 int minchild = parent * 2 + 1; while (minchild < size ) { //2.找出“长子” if (minchild + 1 < size && a[minchild+1] > a[minchild]) { minchild = minchild + 1; } //3.比较父子 if (a[minchild] > a[parent]) { //子节点>父节点,交换 swap(&a[minchild], &a[parent]); //迭代 parent = minchild; minchild = parent * 2 + 1; } else { break; } } }
计算时间复杂度:
理解了建堆的方法,我们就可以考虑堆的应用->堆排序
四、堆排序
我们直到大堆,小堆的特性以后可以隐约地感觉这种结构可以发挥数据的选择,排序就是一种数据有序的要求,这里强调的是大堆小堆并未完全实现数组有序,由上面的例子可以看出大小堆并非有序,但堆顶元素具有Max,Min的性质!
现在问一个问题:排升序是建大堆,还是小堆?排降序呢?停下来自己思考一下!
很多人会不暇思索地回答:“小堆!”,原因是小堆堆顶正好是最小的!现上图来帮你分析一下为啥小堆排升序是效率很低的。
现在上代码~
void HeapSort(int*a,int n) { //利用向下调整法建大堆 时间复杂度0(N) for (int i = (n-2)/2;i>=0;i--) { AdjustDown(a, n, i); } //排序 时间复杂度0(N*logN) for (int i = 1;i < n;i++) { swap(&a[0], &a[n-i]); //再向下建大堆 AdjustDown(a, n-i, 0); } } void TestHeapSort() { int arr[] = { 9,7,2,6,3,5,1,4,8 }; HeapSort(arr, sizeof(arr) / sizeof(arr[0])); for (int i = 0;i < sizeof(arr) / sizeof(arr[0]);i++) { printf("%d ", arr[i]); } }
五、TopK问题
TopK问题:找出N个数里面最大/最小的前K个问题。 比如:未央区排名前10的泡馍,西安交通大学王者荣耀排名前10的韩信,全国排名前10的李白。等等问题都是Topk问题。
方法1:直接堆排序 时间复杂度O(N*logN)
方法二:建大堆,取堆顶,与最后一个值交换然后继续建堆 时间复杂度O(N+K*logN) 该方法适用于N较小时,当N很大该方法效率不如方法三
方法三:对前K个数建小堆,然后遍历后N-K个数,如果该数比小堆堆顶大就替换,替换完之后重新建小堆,重复直到遍历结束。 时间复杂度O(K+(N-K)*logK) 适用于N很大的情况下
现上法二、方法三代码~
方法二:
void PrintTopK1(int* a, int n, int k) { assert(k < n&& k>0); //建大堆 for (int i = (n - 2) / 2;i >= 0;i--) { AdjustDown(a, n, i); } //取TopK int i = 1; while (i<=k) { printf("%d ", a[0]); swap(&a[0], &a[n - i]); AdjustDown(a, n - i, 0); i++; } } void TestTopk() { int arr[] = { 9,7,2,6,3,5,1,4,8 }; PrintTopK1(arr, sizeof(arr) / sizeof(int), 3);//建大堆 N较小情况下选择 }
方法三:
//随机生成N个随机数 控制随机数数值范围,然后把文件中几个值手动修改中成几个>随机数最大值的值 void CreateData(int N) { srand((unsigned int)time(NULL)); FILE* fout = fopen("Heap.txt", "w"); if (fout == NULL) { perror("fopen failed"); exit(-1); } for (int i = 0;i < N;i++) { fprintf(fout, "%d ", rand()%1000); } fclose(fout); } void PrintTopK2(const char*filename, int N, int k) { FILE* fout = fopen(filename, "r"); //读取k个数据 空间复杂度0(k) int* a = (int*)malloc(sizeof(int) * k); for (int i = 0;i < k;i++) { fscanf(fout, "%d", &a[i]); } //向下调整法建立小堆 时间复杂度0(k) for (int i = (k - 2) / 2;i >= 0;i--) { AdjustDown(a, k, i); } //继续读取,寻找大值,然后重新建堆 时间复杂度(N-k)*logk int val; while (fscanf(fout, "%d", &val) != EOF) { if (val > a[0]) { a[0] = val; AdjustDown(a, k, 0); } } for (int i = 0;i < k;i++) { printf("%d ", a[i]); } free(a); fclose(fout); } void TestTopk() { int N = 1000; CreateData(N); PrintTopK2("Heap.txt", N, 10);//建小堆 适合N数据比较大的情况 }
总结
堆是数据结构中比较重要的一部分,它可以应用到排序的算法中。对于堆,我们一定要掌握其建堆的核心思想,这是重中之重!最后,希望这篇文章对你有益,如果你发现哪里有问题,希望您能不吝赐教。