数据结构 - 堆

介绍堆之前,我们需要先了解树这个概念.树的概念有⼀个特殊的结点称为根结点根结点没有前驱结点。树形结构中⼦树之间不能有交集否则就不是树形结构.⼀棵N个结点的树有N-1条边.树的相关术语树的表示孩⼦兄弟表⽰法树结构相对线性表就⽐较复杂了要存储表⽰起来就⽐较⿇烦了既然保存值域也要保存结点和结点之间的关系实际中树有很多种表⽰⽅式如双亲表⽰法孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表⽰法等。我们这⾥就简单的了解其中最常⽤的孩⼦兄弟表⽰法。structTreeNode{intdata;structTreeNode*child;//指向左边开始的第一个孩子结点structTreeNode*brother;//指向右边的下一个兄弟结点};如图这种表示法可以包含任意的结点。树形结构实际运用场景⽂件系统是计算机存储和管理⽂件的⼀种⽅式它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中树结构被⼴泛应⽤它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间的关联。二叉树在树形结构中我们最常⽤的就是⼆叉树⼀棵⼆叉树是结点的⼀个有限集合该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。从上图可以看出⼆叉树具备以下特点⼆叉树不存在度⼤于 2 的结点⼆叉树的⼦树有左右之分次序不能颠倒因此⼆叉树是有序树特殊的二叉树满二叉树完全二叉树贴图仔细理解。二叉树存储结构⼆叉树⼀般可以使⽤两种结构存储⼀种顺序结构⼀种链式结构。顺序结构存储就是使用数组来存储⼀般使⽤数组只适合表⽰完全⼆叉树因为不是完全⼆叉树会有空间的浪费完全⼆叉树更适合使⽤顺序结构存储。链式存储我们以后在讲。现实中我们通常把堆⼀种⼆叉树使⽤顺序结构的数组来存储需要注意的是这⾥的堆和操作系统虚拟进程地址空间中的堆是两回事⼀个是数据结构⼀个是操作系统中管理内存的⼀块区域分段。堆堆是一种特殊的完全二叉树并且每个节点都大于等于或小于等于其子节点大根堆和小根堆大堆每个节点都大于其子节点根节点是最大值。小堆每个节点都小于其子节点根节点是最小值。堆的实现入堆在插入数据后还需要调整堆----保证插入后的结构还是堆结构。堆的向上调整算法出堆在堆结构里删除数据只能操作堆顶。向下调整算法接下来用代码来展示堆和其功能实现Heap.h#define_CRT_SECURE_NO_WARNINGS1#includestdio.h#includestdlib.h#includeassert.h#includestdbool.htypedefintHeapDataType;typedefstructHeap{HeapDataType*arr;intsize;intcapacity;}Heap;voidHeapInit(Heap*php);voidHeapDestroy(Heap*php);boolHeapEmpty(Heap*php);voidHeapPush(Heap*php,HeapDataType x);voidAdjustUp(HeapDataType*arr,intchild);//这里直接传arr就行不需要传结构体孩子结点的类型是int不是HeapDataType,因为这是数组的下标voidHeapPrint(Heap*php);voidHeapPop(Heap*php);voidAdjustDown(HeapDataType*arr,intparent,intn);//注意形参设计HeapDataTypeHeapTop(Heap*php);Heap.c#define_CRT_SECURE_NO_WARNINGS1#includeheap.hvoidHeapInit(Heap*php){php-arrNULL;php-sizephp-capacity0;}voidHeapDestroy(Heap*php){if(php-arr){free(php-arr);}php-arrNULL;php-sizephp-capacity0;}boolHeapEmpty(Heap*php)//学习怎么判空,头文件stdbool.h{assert(php);returnphp-size0;}voidHeapPrint(Heap*php){for(inti0;iphp-size;i){printf(%d ,php-arr[i]);}printf(\n);}voidSwap(int*x,int*y){intmid*x;*x*y;*ymid;}voidAdjustUp(HeapDataType*arr,intchild){intparent;while(child0){parent(child-1)/2;//创建大堆//创建小堆if(arr[child]arr[parent]){Swap(arr[child],arr[parent]);//传地址childparent;}else{break;}}}voidHeapPush(Heap*php,HeapDataType x){assert(php);if(php-sizephp-capacity){intnewcapacityphp-capacity0?4:2*php-capacity;HeapDataType*tmp(HeapDataType*)realloc(php-arr,newcapacity*sizeof(HeapDataType));if(tmpNULL){perror(realloc);}php-arrtmp;php-capacitynewcapacity;}php-arr[php-size]x;//向上调整AdjustUp(php-arr,php-size);php-size;}voidAdjustDown(HeapDataType*arr,intparent,intn){intchildparent*21;while(childn){if(arr[child1]arr[child]child1n){child;}//我们这里选择排列后的数组是//升序大堆 //降序小堆 if(arr[child]arr[parent]){Swap(arr[child],arr[parent]);parentchild;childparent*21;}else{break;}}}voidHeapPop(Heap*php){assert(!HeapEmpty(php));Swap(php-arr[0],php-arr[php-size-1]);php-size--;AdjustDown(php-arr,0,php-size);}HeapDataTypeHeapTop(Heap*php){assert(!HeapEmpty(php));returnphp-arr[0];}test.c#define_CRT_SECURE_NO_WARNINGS1#includeheap.h//struct TreeNode {// int data;// struct TreeNode* child;//指向左边开始的第一个孩子结点// struct TreeNode* brother;//指向右边的下一个兄弟结点//};voidtest01(){Heap heap;HeapInit(heap);HeapPush(heap,3);HeapPush(heap,2);HeapPush(heap,6);HeapPush(heap,9);HeapPush(heap,4);HeapPrint(heap);HeapPop(heap);HeapPrint(heap);HeapPop(heap);HeapPrint(heap);HeapPop(heap);HeapPrint(heap);HeapPop(heap);HeapPrint(heap);HeapPop(heap);HeapPrint(heap);HeapPop(heap);HeapPrint(heap);HeapDestroy(heap);}intmain(){test01();return0;}堆排序基于上面我们实现的堆的功能我们可以编写这样的一段代码voidHeapSort(int*arr,intn){Heap heap;HeapInit(heap);for(inti0;in;i){HeapPush(heap,arr[i]);}inti0;while(!HeapEmpty(heap)){arr[i]HeapTop(heap);printf(%d ,arr[i]);HeapPop(heap);i;}HeapDestroy(heap);}intmain(){intarr[6]{6,3,0,1,8,2};HeapSort(arr,6);return0;}难道这种写法就是传说中的堆排序吗当然不是了。因为这种写法还要去创建一个堆结构这会非常麻烦,难道面试的时候你还去写一堆堆结构后再来实现排序嘛。堆排序-------是借助堆的思想来排序接下来我们来实现真正的堆排序voidAdjustDown(HeapDataType*arr,intparent,intn){intchildparent*21;while(childn){if(arr[child1]arr[child]child1n){child;}//我们这里选择排列后的数组是//升序大堆 //降序小堆 if(arr[child]arr[parent]){Swap(arr[child],arr[parent]);parentchild;childparent*21;}else{break;}}voidAdjustUp(int*arr,intchild){intparent(child-1)/2;while(child0){if(arr[child]arr[parent]){swap(arr[child],arr[parent]);childparent;parent(child-1)/2;}else{break;}}}voidHpSort(int*arr,intn){assert(arr);//建堆--向下调整算法建堆intparent(n-1-1)/2;for(parent;parent0;parent--){AdjustDown(arr,parent,n);}//向上调整建堆/*for (int i 1;i x;i) { AdjustUp(arr, i); }*/// 堆排序intendn-1;while(end){Swap(arr[0],arr[end]);AdjustDown(arr,0,end);end--;}}intmain(){intarr[6]{6,3,4,1,8,2};//HeapSort01(arr, 6);HpSort(arr,6);for(inti0;i6;i){printf(%d ,arr[i]);}return0;}为什么用向下构建堆算法要从最后一个非叶子节点开始· 如果从根节点 0 开始它的左右子树还没有被处理成堆因为子节点可能本身就比孙子小导致一次下沉后上层看似满足但下层结构可能已被破坏。· 因此我们必须自底向上构建先保证最小的子树是堆然后逐步扩大。从最后一个非叶子节点开始它只有叶子作为孩子叶子本身就是堆所以函数可以正确把它调整成堆。然后倒着向上每次处理一个更高节点时它的左右子树都已经满足堆性质函数就能正常工作根据数组需要的排序来建堆1.排升序 ——建大堆2.排降序 ——建小堆复杂度我们来讨论下向上调整算法建堆和向下调整算法建堆和堆排序的时间复杂度向上调整算法建堆的时间复杂度注意不是向上调整算法的复杂度O(nlogn),粗略的理解上面的结点少向上的次数也少下面的结点多向上的次数多。向下调整算法建堆的时间复杂度O(n),粗略的理解上面的结点少向下的次数多下面的结点多但向下的次数少。堆排序的时间复杂度我们来看第二个循环的复杂度TOP-K问题TOP-K问题即求数据结合中前K个最⼤的元素或者最⼩的元素⼀般情况下数据量都⽐较⼤。比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的⽅式就是⽤堆来解决基本思路如下1⽤数据集合中前K个元素来建堆求前k个最⼤的元素则建⼩堆求前k个最⼩的元素则建⼤堆2⽤剩余的N-K个元素依次与堆顶元素来⽐较不满⾜则替换堆顶元素将剩余N-K个元素依次与堆顶元素⽐完之后堆中剩余的K个元素就是所求的前K个最⼩或者最⼤的元素voidCreateNDate(){// 造数据intn100000;srand(time(0));constchar*filedata.txt;FILE*finfopen(file,w);if(finNULL){perror(fopen error);return;}for(inti0;in;i){intx(rand()i)%1000000;fprintf(fin,%d\n,x);}fclose(fin);}voidTopK(){intk0;printf(请输入K);scanf(%d,k);constchar*filedata.txt;FILE*foutfopen(file,r);if(foutNULL){perror(fopen fail!);exit(1);}//找最大的前K个数据建小堆int*minHeap(int*)malloc(sizeof(int)*k);if(minHeapNULL){perror(malloc fail!);exit(2);}for(inti0;ik;i){fscanf(fout,%d,minHeap[i]);}//minHeap -- 向下调整建堆for(inti(k-1-1)/2;i0;i--){AdjustDown(minHeap,i,k);}//遍历剩下的n-k个数据跟堆顶比较堆顶小替换堆顶元素intx0;while(fscanf(fout,%d,x)!EOF){//X minHeap-topif(xminHeap[0]){minHeap[0]x;AdjustDown(minHeap,0,k);}}for(inti0;ik;i){printf(%d ,minHeap[i]);}fclose(fout);}时间复杂度O(n) k(n-k)log(k)