启铭网站建设,wordpress 短信,如何免费搭建自己的网站,网站建设 地址: 上海石门二路OVERVIEW 栈与堆的区别一、程序内存分区中的堆与栈1.栈2.堆3.堆栈 二、数据结构中的堆与栈1.栈2.堆 三、堆的深入1.堆插入2.堆删除#xff1a;3.堆建立#xff1a;4.堆排序#xff1a;5.堆实现优先队列#xff1a;6.堆与栈的相关练习 栈与堆的区别 自整理#xff0c;… OVERVIEW 栈与堆的区别一、程序内存分区中的堆与栈1.栈2.堆3.堆栈 二、数据结构中的堆与栈1.栈2.堆 三、堆的深入1.堆插入2.堆删除3.堆建立4.堆排序5.堆实现优先队列6.堆与栈的相关练习 栈与堆的区别 自整理以下为主要参考文章
堆与栈的对比一文读懂堆与栈的区别_堆和栈的区别_恋喵大鲤鱼的博客-CSDN博客堆与栈的理解什么是堆? 什么是栈 - 知乎 (zhihu.com)用堆实现优先队列用堆实现优先级队列Priority Queue_优先队列用堆实现_t_wu的博客-CSDN博客用堆实现优先队列什么是优先队列 - 知乎 (zhihu.com)深入底层内存中的堆和栈到底是什么 | 洛斯里克的大书库 (kimihe.com)Python版本Codify (wzy-codify.com)
在理解堆与栈概念时需要放到具体的场景下因为不同场景下堆与栈代表不同的含义
场景1程序内存布局场景下堆与栈表示两种内存管理方式。场景2数据结构场景下堆与栈表示两种常用的数据结构。
一、程序内存分区中的堆与栈
堆与栈的空间都是分配在内存上 1.栈
其中函数中定义的局部变量按照先后定义的顺序依次压入栈中也就是说相邻变量的地址之间不会存在其它变量。栈的内存地址生长方向与堆相反由高到低所以后定义的变量地址低于先定义的变量。栈中存储的数据的生命周期随着函数的执行完成而结束。
2.堆
但需要注意的是后申请的内存空间并不一定在先申请的内存空间的后面原因是先申请的内存空间一旦被释放后申请的内存空间则会利用先前被释放的内存从而导致先后分配的内存空间在地址上不存在先后关系。堆的内存地址生长方向与栈相反由低到高堆中存储的数据若未释放则其生命周期等同于程序的生命周期。 注关于堆上内存空间的分配过程首先应该知道操作系统有一个记录空闲内存地址的链表当系统收到程序的申请时会遍历该链表寻找第一个空间大于所申请空间的堆节点然后将该节点从空闲节点链表中删除并将该节点的空间分配给程序。另外对于大多数系统会在这块内存空间中的首地址处记录本次分配的大小这样代码中的delete语句才能正确地释放本内存空间。由于找到的堆节点的大小不一定正好等于申请的大小系统会自动地将多余的那部分重新放入空闲链表。 3.堆栈
堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式主要有如下几种区别
不同点堆栈1.管理方式不同栈由操作系统自动分配释放无需手动控制堆的申请和释放工作由开发者控制容易产生内存泄漏2.空间大小不同每个进程拥有的栈大小要远远小于堆大小理论上进程可申请的堆大小为虚拟内存大小进程栈的大小 64bits 的 Windows 默认 1MB64bits 的 Linux 默认 10MB3.生长方向不同堆的生长方向向上内存地址由低到高栈的生长方向向下内存地址由高到低4.分配方式不同堆都是动态分配的没有静态分配的堆栈有 2 种分配方式静态分配和动态分配。静态分配是由操作系统完成的比如局部变量的分配。动态分配由alloca()函数分配但是栈的动态分配和堆是不同的它的动态分配是由操作系统进行释放无需手动实现。5.分配效率不同栈由操作系统自动分配会在硬件层级对栈提供支持分配专门的寄存器存放栈的地址压栈出栈都有专门的指令执行这就决定了栈的效率比较高堆则是由C/C提供的库函数或运算符来完成申请与管理实现机制较为复杂频繁的内存申请容易产生内存碎片。显然堆的效率比栈要低得多6.存放内容不同栈存放的内容有函数返回地址、相关参数、局部变量和寄存器内容等。当主函数调用另外一个函数的时候要对当前函数执行断点进行保存这需要使用栈来实现。首先入栈的是主函数下一条语句的地址即扩展指针寄存器的内容EIP然后是当前栈帧的底部地址即扩展基址指针寄存器内容EBP再然后是被调函数的实参等一般情况下是按照从右向左的顺序入栈之后是被调函数的局部变量注意静态变量是存放在数据段或者BSS段是不入栈的。出栈的顺序正好相反最终栈顶指向主函数下一条语句的地址主程序又从该地址开始执行。堆一般情况堆顶使用一个字节的空间来存放堆的大小而堆中具体存放内容是由程序员来填充的。7.产生内存碎片栈与数据结构中的栈原理相同在弹出一个元素之前上个元素已经弹出了不会产生内存碎片而不停的调用malloc/new、free/delete则会产生很多的内存碎片。8.线程安全栈内存是为线程留出的临时空间每一个线程都有其固定的栈空间栈空间存储的数据只能被当前线程访问线程安全堆内存大小不固定、空间由开发者动态分配可以动态扩容堆内存可以被一个进程内的所有线程访问线程不安全9.访问权限不同函数之间的栈数据不能够共享在启动线程的时候实际上是启动函数其具有自己的栈线程之间的栈数据时不能够共享的堆属于在进程上的堆只要在进程上application内所有的线程都可以访问堆上的数据。堆在不同的语言下管理释放的方式不同垃圾回收机制、free、
从以上可以看到
堆由于大量malloc()/free()或new/delete的使用容易造成大量的内存碎片并且可能引发用户态和核心态的切换效率较低。栈在程序中应用较为广泛最常见的是函数的调用过程由栈来实现函数返回地址、EBP、实参和局部变量都采用栈的方式存放。虽然栈有众多的好处但是由于和堆相比不是那么灵活有时候分配大量的内存空间主要还是用堆。无论是堆还是栈在内存使用时都要防止非法越界越界导致的非法内存访问可能会摧毁程序的堆、栈数据轻则导致程序运行处于不确定状态获取不到预期结果重则导致程序异常崩溃这些都是我们编程时与内存打交道时应该注意的问题。
二、数据结构中的堆与栈
1.栈
栈栈是一种运算受限的线性表其限制是指只仅允许在表的一端进行插入和删除操作。具有FILO先进后出的特性。
2.堆
堆堆是一种常用的树形结构是一种特殊的完全二叉树满足所有节点的值不大于或不小于其父节点的值的完全二叉树被称之为堆。
堆这一特性称为堆序性因此在一个堆中根节点是最大 or 最小的节点。如果根节点最小称之为小根堆根节点最大称之为大根堆。堆的左右孩子没有大小的顺序。 堆的存储一般都用数组来存储堆i节点的父节点下标就为(i–1)/2它的左右子节点下标分别为 2∗i1 和 2∗i2
堆可以用来排序也可以用来实现优先级队列而优先级队列是搜索的基础。
三、堆的深入
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] temp) break;//如果父节点不大于新插入的元素停止寻找a[i]a[j];//把较大的子节点往下移动,替换它的子节点 i j; j (i-1)/2; } a[i] temp;
} 因此插入数据到最小堆时
// 在最小堆中加入新的数据data
// a数组index插入的下标
void minHeapAddNumber(int a[], int index, int data) { a[index] data; minHeapFixUp(a, index);
}2.堆删除
删除一个元素总是发生在堆顶因为堆顶的元素是最小的小顶堆中。数组中最后一个元素用来填补空缺位置然后对顶部元素进行下沉如果左右孩子有比自己小的则选择选择最小的那个进行交换。重复进行下沉操作以满足堆的条件。
按照堆删除的说明堆中每次都只能删除第0个数据。为了便于重建堆实际的操作是将数组最后一个数据与根节点交换然后再从根节点开始进行一次从上向下的调整。
调整时先在左右儿子节点中找最小的如果父节点不大于这个最小的子节点说明不需要调整了反之将最小的子节点换到父节点的位置。此时父节点实际上并不需要换到最小子节点的位置因为这不是父节点的最终位置。但逻辑上父节点替换了最小的子节点然后再考虑父节点对后面的节点的影响。堆元素的删除导致的堆调整其整个过程就是将根节点进行“下沉”处理。
// minHeapFixDown 小顶堆结点下沉操作。
// a 为数组len 为结点总数从 index 结点开始调整index 从 0 开始计算 index 其子结点为 2*index1, 2*index2len/2-1 为最后一个非叶子结点。
void minHeapFixDown(int a[],int len,int index) {// index 为叶子节点不用调整。if(index(len/2-1)) return;int tmpa[index];lastIndexindex;// 当下沉到叶子节点时就不用调整了。while(indexlen/2-1) {// 如果左子节点小于待调整节点if(a[2*index1]tmp) {lastIndex 2*index1;}//如果存在右子节点且小于左子节点和待调整节点if(2*index2len a[2*index2]a[2*index1] a[2*index2]tmp) {lastIndex2*index2;}//如果左右子节点有一个小于待调整节点选择最小子节点进行上浮if(lastIndex!index) {a[index]a[lastIndex];indexlastIndex;} else break; // 否则待调整节点不用下沉调整}// 将待调整节点放到最后的位置。a[lastIndex]tmp;
}根据堆删除的下沉思想可以有不同版本的代码实现以上是和孙凛同学一起讨论出的一个版本在这里感谢他的参与读者可另行给出。个人体会这里建议大家根据对堆调整过程的理解写出自己的代码切勿看示例代码去理解算法而是理解算法思想写出代码否则很快就会忘记。
3.堆建立 注有了堆的插入和删除后再考虑下如何对一个数据进行堆化操作。 以数组存储元素时具有对应的树表示形式但树有可能并不满足堆的性质需要重新排列元素才能建立堆化的树。
单结点的二叉树是堆无需调整树中的叶子结点在完全二叉树中所有以叶子结点为根的子树是堆无需调整堆的调整只需要从最后一个非叶子结点开始即可需要依次将以序号为n/2、n/2-1、…1的结点为根的子树均调整为堆即可筛选需从第n/2个元素开始 将初始无序序列调整成小根堆筛选过程可以利用以算法实现
// makeMinHeap 建立最小堆。
// a:数组n数组长度。
void makeMinHeap(int a[], int n) {for (int i n/2-1; i 0; i--) {minHeapFixDown(a, i, n);}
}4.堆排序
思路是每次都把堆顶的元素和堆尾的元素交换然后把除了堆尾的那个元素组成的堆进行堆化就是把堆顶的元素进行下沉)不断重复直至堆为空为止。
堆排序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 ilen-1;i0;--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); }
}稳定性堆排序是不稳定排序。堆排序性能分析。由于每次重新恢复堆的时间复杂度为O(logN)共N-1次堆调整操作再加上前面建立堆时N/2次向下调整每次调整时间复杂度也为O(logN)。两次操作时间复杂度相加还是O(NlogN)故堆排序的时间复杂度为O(NlogN)最坏情况如果待排序数组是有序的仍然需要O(NlogN)复杂度的比较操作只是少了移动的操作最好情况如果待排序数组是逆序的不仅需要O(NlogN)复杂度的比较操作而且需要O(NlogN)复杂度的交换操作总的时间复杂度还是O(NlogN)。因此堆排序和快速排序在效率上是差不多的但是堆排序一般优于快速排序的重要一点是数据的初始分布情况对堆排序的效率没有大的影响。
5.堆实现优先队列
待完善
6.堆与栈的相关练习
Leetcode232.用栈实现队列https://leetcode.cn/problems/implement-queue-using-stacks/description/Leetcode225.用队列实现栈https://leetcode.cn/problems/implement-stack-using-queues/剑指offer09.用两个栈实现队列https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/Leetcode1441.用栈构建数组https://leetcode.cn/problems/build-an-array-with-stack-operations/
相关文章：
