一文读懂堆与栈的区别 |
您所在的位置：网站首页 › 小米11liteNE和没有NE区别 › 一文读懂堆与栈的区别 |
一文读懂堆与栈的区别
|
大咖好呀，我是恋喵大鲤鱼。 鄙人开源书籍 《Go 编码建议》上线拉，欢迎大家协同共建。 鄙人开源书籍 《后台开发命令365》上线拉，欢迎大家协同共建。 鄙人开源书籍 《MySQL 快速上手》上线拉，欢迎大家协同共建。 文章目录 0.前言1.程序内存分区中的堆与栈1.1 栈简介1.2 堆简介1.3 堆与栈区别 2.数据结构中的堆与栈2.1 栈简介2.2 堆简介2.2.1 堆的性质2.2.2 堆的基本操作2.2.3 堆操作实现2.2.4 堆的具体应用——堆排序 参考文献杂注 0.前言堆（Heap）与栈（Stack）是开发人员必须面对的两个概念，在理解这两个概念时，需要放到具体的场景下，因为不同场景下，堆与栈代表不同的含义。一般情况下，有两层含义： （1）程序内存布局场景下，堆与栈表示两种内存管理方式。 （2）数据结构场景下，堆与栈表示两种常用的数据结构。 1.程序内存分区中的堆与栈 1.1 栈简介栈由操作系统自动分配释放 ，用于存放函数的参数值、局部变量等，其操作方式类似于数据结构中的栈。参考如下代码： int main() { int b; //栈 char s[] = "abc"; //栈 char *p2; //栈 }其中函数中定义的局部变量按照先后定义的顺序依次压入栈中，也就是说相邻变量的地址之间不会存在其它变量。栈的内存地址生长方向与堆相反，由高到底，所以后定义的变量地址低于先定义的变量，比如上面代码中变量 s 的地址小于变量 b 的地址，p2 地址小于 s 的地址。栈中存储的数据的生命周期随着函数的执行完成而结束。 1.2 堆简介堆由开发人员分配和释放， 若开发人员不释放，程序结束时由 OS 回收，分配方式类似于链表。参考如下代码： int main() { // C 中用 malloc() 函数申请 char* p1 = (char *)malloc(10); cout SeqStack* s=(SeqStack*)malloc(sizeof(SeqStack)); if(!s) { printf("空间不足\n"); return NULL; } else { s->top = -1; return s; } } //判断栈是否为空 bool isEmptySeqStack(SeqStack* s) { if (s->top == -1) return true; else return false; } //入栈，返回-1失败，0成功 int pushSeqStack(SeqStack* s, DataType x) { if(s->top == MAXSIZE-1) { return -1;//栈满不能入栈 } else { s->top++; s->data[s->top] = x; return 0; } } //出栈，返回-1失败，0成功 int popSeqStack(SeqStack* s, DataType* x) { if(isEmptySeqStack(s)) { return -1;//栈空不能出栈 } else { *x = s->data[s->top]; s->top--; return 0; } } //取栈顶元素，返回-1失败，0成功 int topSeqStack(SeqStack* s,DataType* x) { if (isEmptySeqStack(s)) return -1; //栈空 else { *x=s->data[s->top]; return 0; } } //打印栈中元素 int printSeqStack(SeqStack* s) { int i; printf("当前栈中的元素:\n"); for (i = s->top; i >= 0; i--) printf("%4d",s->data[i]); printf("\n"); return 0; } //test int main() { SeqStack* seqStack=initSeqStack(); if(seqStack) { //将4、5、7分别入栈 pushSeqStack(seqStack,4); pushSeqStack(seqStack,5); pushSeqStack(seqStack,7); //打印栈内所有元素 printSeqStack(seqStack); //获取栈顶元素 DataType x=0; int ret=topSeqStack(seqStack,&x); if(0==ret) { printf("top element is %d\n",x); } //将栈顶元素出栈 ret=popSeqStack(seqStack,&x); if(0==ret) { printf("pop top element is %d\n",x); } } return 0; }运行上面的程序，输出结果： 当前栈中的元素: 7 5 4 top element is 7 pop top element is 7 2.2 堆简介 2.2.1 堆的性质堆是一种常用的树形结构，是一种特殊的完全二叉树，当且仅当满足所有节点的值总是不大于或不小于其父节点的值的完全二叉树被称之为堆。堆的这一特性称之为堆序性。因此，在一个堆中，根节点是最大（或最小）节点。如果根节点最小，称之为小顶堆（或小根堆），如果根节点最大，称之为大顶堆（或大根堆）。堆的左右孩子没有大小的顺序。下面是一个小顶堆示例： 以最小堆为例，如果以数组存储元素时，一个数组具有对应的树表示形式，但树并不满足堆的条件，需要重新排列元素，可以建立“堆化”的树。 将一个新元素插入到数组末尾，如果新构成的二叉树不满足堆的性质，需要将新元素在其到堆顶的路径上，找到属于自己的位置，即进行上浮操作。 下图演示了插入 15 时，堆的调整。 删除一个元素总是发生在堆顶，因为堆顶的元素是最小的（小顶堆中）。数组中最后一个元素用来填补空缺位置，然后对顶部元素进行下沉，如果左右孩子有比自己小的，则选择选择最小的那个进行交换。重复进行下沉操作，以满足堆的条件。 （1）插入实现 每次插入都是将新数据放在数组最后。可以发现从这个新数据的父节点到根节点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中，这就类似于直接插入排序中将一个数据并入到有序区间中，这是节点“上浮”调整。不难写出插入一个新数据时堆的调整代码： // 新加入i节点,其父节点为(i-1)/2 // 参数：a：数组，i：新插入元素在数组中的下标 void minHeapFixUp(int a[], int i) { int j, temp; temp = a[i]; j = (i-1)/2; //父节点 while (j >= 0 && i != 0) { if (a[j] // index 为叶子节点不用调整。 if(index>(len/2-1)) return; int tmp=a[index]; lastIndex=index; // 当下沉到叶子节点时，就不用调整了。 while(index lastIndex = 2*index+1; } //如果存在右子节点且小于左子节点和待调整节点 if(2*index+2 a[index]=a[lastIndex]; index=lastIndex; } else break; // 否则待调整节点不用下沉调整 } // 将待调整节点放到最后的位置。 a[lastIndex]=tmp; }根据堆删除的下沉思想，可以有不同版本的代码实现，以上是和孙凛同学一起讨论出的一个版本，在这里感谢他的参与，读者可另行给出。个人体会，这里建议大家根据对堆调整过程的理解，写出自己的代码，切勿看示例代码去理解算法，而是理解算法思想写出代码，否则很快就会忘记。 （3）建堆 有了堆的插入和删除后，再考虑下如何对一个数据进行堆化操作。要一个一个的从数组中取出数据来建立堆吧，不用！先看一个数组，如下图： 很明显，对叶子结点来说，可以认为它已经是一个合法的堆了，即 20，60，65，4，49 都分别是一个合法的堆。只要从 A[4]=50 开始向下调整就可以了。然后再取 A[3] = 30，A[2] = 17，A[1] = 12，A[0] = 9 分别作一次向下调整操作就可以了。 下图展示了这些步骤： 堆排序（Heapsort）是堆的一个经典应用，有了上面对堆的了解，不难实现堆排序。由于堆也是用数组来存储的，故对数组进行堆化后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换，再对A[0…n - 3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。有点类似于直接选择排序。 因此，完成堆排序并没有用到前面说明的插入操作，只用到了建堆和节点向下调整的操作，堆排序的操作如下： // array:待排序数组，len：数组长度 void heapSort(int array[],int len) { // 建堆 makeMinHeap(array,len); // 最后一个叶子节点和根节点交换，并进行堆调整，交换次数为len-1次 for(int i=len-1;i>0;--i) { //最后一个叶子节点交换 array[i]=array[i]+array[0]; array[0]=array[i]-array[0]; array[i]=array[i]-array[0]; // 堆调整 minHeapFixDown(array, 0, len-i-1); } }（1）稳定性。堆排序是不稳定排序。 （2）堆排序性能分析。由于每次重新恢复堆的时间复杂度为O(logN)，共N-1次堆调整操作，再加上前面建立堆时N/2次向下调整，每次调整时间复杂度也为O(logN)。两次操作时间复杂度相加还是O(NlogN)，故堆排序的时间复杂度为O(NlogN)。 最坏情况：如果待排序数组是有序的，仍然需要O(NlogN)复杂度的比较操作，只是少了移动的操作； 最好情况：如果待排序数组是逆序的，不仅需要O(NlogN)复杂度的比较操作，而且需要O(NlogN)复杂度的交换操作，总的时间复杂度还是O(NlogN)。 因此，堆排序和快速排序在效率上是差不多的，但是堆排序一般优于快速排序的重要一点是数据的初始分布情况对堆排序的效率没有大的影响。 参考文献[1] 浅谈堆和栈的区别 [2] 栈内存和堆内存的区别 [3] 浅谈内存分配方式以及堆和栈的区别（很清楚） [4] C++函数调用过程深入分析 [5] 十种排序算法 杂注我的博客即将搬运同步至腾讯云+社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2z2o0f9ecoo44 |
【本文地址】