版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_38004638/article/details/91043461

堆（Heap）与栈（Stack）是开发人员必须面对的两个概念，在理解这两个概念时，需要放到具体的场景下，因为不同场景下，堆与栈代表不同的含义。一般情况下，有两层含义： （1）程序内存布局场景下，堆与栈表示的是两种内存管理方式； （2）数据结构场景下，堆与栈表示两种常用的数据结构。

在说堆和栈之前，我们先说一下JVM（虚拟机）内存的划分：

Java程序在运行时都要开辟空间，任何软件在运行时都要在内存中开辟空间，Java虚拟机运行时也是要开辟空间的。JVM运行时在内存中开辟一片内存区域，启动时在自己的内存区域中进行更细致的划分，因为虚拟机中每一片内存处理的方式都不同，所以要单独进行管理。

JVM内存的划分有五片：

1. 寄存器；

2. 本地方法区；

3. 方法区；

4. 栈内存；

5. 堆内存。

栈由操作系统自动分配释放 ，用于存放函数的参数值、局部变量等，其操作方式类似于数据结构中的栈。

栈内存首先是一片内存区域，存储的都是局部变量，凡是定义在方法中的都是局部变量（方法外的是全局变量），for循环内部定义的也是局部变量，是先加载函数才能进行局部变量的定义，所以方法先进栈，然后再定义变量，变量有自己的作用域，一旦离开作用域，变量就会被释放。栈内存的更新速度很快，因为局部变量的生命周期都很短。

栈的优势：存取速度比堆快，仅次于CPU中的寄存器，栈数据可以共享。 缺点：存在栈中的数据大小与生存周期时确定的，缺乏灵活性。栈中主要存放一些基本类型的变量int, short, long, byte, float, double, boolean, char(注意，并没有string的基本类型)和对象句柄。

特殊性：存在栈中的数据可以共享，假设我们同时定义：

int a = 3; int b = 3;

编译器先处理int a = 3;首先它会在栈中创建一个变量为a的引用，然后查找栈中是否有3这个值，如果没找到，将3存放进来，然后将a 指向3.。接着处理int b = 3;在创建完b的引用变量后，因为在栈中已经有了3这个值。这样，就出现了a与b同时指向3的情况。如果再令a = 4 ;那么编译器会重新搜索栈中是否有4值，如果没有，则将4存放进来，并令a指向4；如果已经有了，则直接将a 指向这个地址。因此a值的改变不会影响b的值

注意：这种数据的共享与两个对象的引用同时指向一个对象的这种共享是不同的，因为这种情况a 的修改并不会影响到b，它是由编译器完成的，有利于节省空间。而一个对象引用变量修改了这个对象的内部状态，会影响到另一个对象引用变量

java的堆是一个运行时数据区，类的对象从中分配内存空间，用来存放由new创建的对象和数组。

通过new . newarray . anewarray和multianewarray等指令建立的都是在堆中，堆中存放的都是实体（对象），实体用于封装数据，而且是封装多个（实体的多个属性），如果一个数据消失，这个实体也没有消失，还可以用，所以堆是不会随时释放的，但是栈不一样，栈里存放的都是单个变量，变量被释放了，那就没有了。堆里的实体虽然不会被释放，但是会被当成垃圾，Java有垃圾回收机制不定时的收取，他们不需要程序代码来显式的释放。

堆的优势是可以动态地分配内存大小，生存期也不必实现高速编译器，因为它在运行时动态分配内存的，java的垃圾收集器会自动收走这些不再使用的数据。但缺点是，由于要在运行时动态分配内存，存取速度较慢。

比如----包装类数据，如Integer, String, Double等将相应的基本数据类型包装起来的类。这些类数据全部存在于堆中，Java用new()语句来显式地告诉编译器，在运行时才根据需要动态创建，因此比较灵活，但缺点是要占用更多的时间。

下面我们通过一个图例详细讲一下堆和栈：

比如主函数里的语句 int [] arr=new int [3];在内存中是怎么被定义的：

主函数先进栈，在栈中定义一个变量arr,接下来为arr赋值，但是右边不是一个具体值，是一个实体。实体创建在堆里，在堆里首先通过new关键字开辟一个空间，内存在存储数据的时候都是通过地址来体现的，地址是一块连续的二进制，然后给这个实体分配一个内存地址。数组都是有一个索引，数组这个实体在堆内存中产生之后每一个空间都会进行默认的初始化（这是堆内存的特点，未初始化的数据是不能用的，但在堆里是可以用的，因为初始化过了，但是在栈里没有），不同的类型初始化的值不一样。所以堆和栈里就创建了变量和实体：

那么堆和栈是怎么联系起来的呢?

我们刚刚说过给堆分配了一个地址，把堆的地址赋给arr，arr就通过地址指向了数组。所以arr想操纵数组时，就通过地址，而不是直接把实体都赋给它。这种我们不再叫他基本数据类型，而叫引用数据类型。称为arr引用了堆内存当中的实体。

如果当int [] arr=null;

arr不做任何指向，null的作用就是取消引用数据类型的指向。

当一个实体，没有引用数据类型指向的时候，它在堆内存中不会被释放，而被当做一个垃圾，在不定时的时间内自动回收，因为Java有一个自动回收机制，（而c++没有，需要程序员手动回收，如果不回收就越堆越多，直到撑满内存溢出，所以Java在内存管理上优于c++）。自动回收机制（程序）自动监测堆里是否有垃圾，如果有，就会自动的做垃圾回收的动作，但是什么时候收不一定。

堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式，主要有如下几种区别：

1.栈内存存储的是函数返回地址、相关参数、局部变量等，而堆内存存储的是实体。

2.栈内存的更新速度要快于堆内存，栈使用的是一级缓存， 调用完毕立即释放。堆则是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定

3.栈内存存放的变量生命周期一旦结束就会被释放，而堆内存存放的实体由程序员分配释放，或被垃圾回收机制回收。

从以上可以看到，堆由于大量malloc()/free()或new/delete的使用，容易造成大量的内存碎片，并且可能引发用户态和核心态的切换，效率较低。栈相比于堆，在程序中应用较为广泛，最常见的是函数的调用过程由栈来实现，函数返回地址、EBP、实参和局部变量都采用栈的方式存放。虽然栈有众多的好处，但是由于和堆相比不是那么灵活，有时候分配大量的内存空间，主要还是用堆。

数据结构中，堆与栈是两个常见的数据结构，理解二者的定义、用法与区别，能够利用堆与栈解决很多实际问题。

栈是一种运算受限的线性表，其限制是指只仅允许在表的一端进行插入和删除操作，这一端被称为栈顶（Top），相对地，把另一端称为栈底（Bottom）。把新元素放到栈顶元素的上面，使之成为新的栈顶元素称作进栈、入栈或压栈（Push）；把栈顶元素删除，使其相邻的元素成为新的栈顶元素称作出栈或退栈（Pop）。这种受限的运算使栈拥有“先进后出”的特性（First In Last Out），简称FILO。

栈分顺序栈和链式栈两种。栈是一种线性结构，所以可以使用数组或链表（单向链表、双向链表或循环链表）作为底层数据结构。使用数组实现的栈叫做顺序栈，使用链表实现的栈叫做链式栈，二者的区别是顺序栈中的元素地址连续，链式栈中的元素地址不连续。

栈的结构如下图所示：

堆是一种常用的树形结构，是一种特殊的完全二叉树，当且仅当满足所有节点的值总是不大于或不小于其父节点的值的完全二叉树被称之为堆。堆的这一特性称之为堆序性。因此，在一个堆中，根节点是最大（或最小）节点。如果根节点最小，称之为小顶堆（或小根堆），如果根节点最大，称之为大顶堆（或大根堆）。堆的左右孩子没有大小的顺序。下面是一个小顶堆示例：

堆的存储一般都用数组来存储堆，i节点的父节点下标就为(i–1)/2 (i – 1) / 2(i–1)/2。它的左右子节点下标分别为 2∗i+1 2 * i + 12∗i+1 和 2∗i+2 2 * i + 22∗i+2。如第0个节点左右子节点下标分别为1和2。

（1）建立 以最小堆为例，如果以数组存储元素时，一个数组具有对应的树表示形式，但树并不满足堆的条件，需要重新排列元素，可以建立“堆化”的树。

（2）插入 将一个新元素插入到表尾，即数组末尾时，如果新构成的二叉树不满足堆的性质，需要重新排列元素，下图演示了插入15时，堆的调整。

（3）删除。 堆排序中，删除一个元素总是发生在堆顶，因为堆顶的元素是最小的（小顶堆中）。表中最后一个元素用来填补空缺位置，结果树被更新以满足堆条件。

（4）如何对一个数据进行堆化操作。要一个一个的从数组中取出数据来建立堆吗

很明显，对叶子节点来说，可以认为它已经是一个合法的堆了即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)。

因此，堆排序和快速排序在效率上是差不多的，但是堆排序一般优于快速排序的重要一点是数据的初始分布情况对堆排序的效率没有大的影响。

https://www.cnblogs.com/jiudianren/p/5671992.html

https://blog.csdn.net/shanchangyi/article/details/51854795

https://blog.csdn.net/K346K346/article/details/80849966

https://blog.csdn.net/pt666/article/details/70876410#commentBox