文章目录
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 栈简介
栈由操作系统自动分配释放 ，用于存放函数的参数值、局部变量等，其操作方式类似于数据结构中的栈。参考如下代码：
1 int main() {
2 int b; //栈
3 char s【】 = "abc"; //栈
4 char p2; //栈
5 }
其中函数中定义的局部变量按照先后定义的顺序依次压入栈中，也就是说相邻变量的地址之间不会存在其它变量。
栈的内存地址生长方向与堆相反，由高到底，所以后定义的变量地址低于先定义的变量，比如上面代码中变量 s 的地址小于变量 b 的地址，p2 地址小于 s 的地址。
栈中存储的数据的生命周期随着函数的执行完成而结束。
1.2 堆简介
堆由开发人员分配和释放， 若开发人员不释放，程序结束时由 OS 回收，分配方式类似于链表。参考如下代码：
1 int main() {
2 // C 中用 malloc() 函数申请
3 char p1 = (char )malloc(10);
4 cout[(int)p1[endl; //输出：00000000003BA0C0
5
6 // 用 free() 函数释放
7 free(p1);
8
9 // C++ 中用 new 运算符申请
10 char p2 = new char【10】;
11 cout [ (int)p2 [ endl; //输出：00000000003BA0C0
12
13 // 用 delete 运算符释放
14 delete【】 p2;
15 }
其中 p1 所指的 10 字节的内存空间与 p2 所指的 10 字节内存空间都是存在于堆。堆的内存地址生长方向与栈相反，由低到高，但需要注意的是，后申请的内存空间并不一定在先申请的内存空间的后面，即 p2 指向的地址并不一定大于 p1 所指向的内存地址，原因是先申请的内存空间一旦被释放，后申请的内存空间则会利用先前被释放的内存，从而导致先后分配的内存空间在地址上不存在先后关系。堆中存储的数据若未释放，则其生命周期等同于程序的生命周期。
关于堆上内存空间的分配过程，首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请空间的堆节点，然后将该节点从空闲节点链表中删除，并将该节点的空间分配给程序。另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样，代码中的delete语句才能正确地释放本内存空间。由于找到的堆节点的大小不一定正好等于申请的大小，系统会自动地将多余的那部分重新放入空闲链表。
1.3 堆与栈区别
堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式，主要有如下几种区别：
（1）管理方式不同。栈由操作系统自动分配释放，无需我们手动控制；堆的申请和释放工作由程序员控制，容易产生内存泄漏；
（2）空间大小不同。每个进程拥有的栈大小要远远小于堆大小。理论上，进程可申请的堆大小为虚拟内存大小，进程栈的大小 64bits 的 Windows 默认 1MB，64bits 的 Linux 默认 10MB；
（3）生长方向不同。堆的生长方向向上，内存地址由低到高；栈的生长方向向下，内存地址由高到低。
（4）分配方式不同。堆都是动态分配的，没有静态分配的堆。栈有 2 种分配方式：静态分配和动态分配。静态分配是由操作系统完成的，比如局部变量的分配。动态分配由alloca()函数分配，但是栈的动态分配和堆是不同的，它的动态分配是由操作系统进行释放，无需我们手工实现。
（5）分配效率不同。栈由操作系统自动分配，会在硬件层级对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是由C/C++提供的库函数或运算符来完成申请与管理，实现机制较为复杂，频繁的内存申请容易产生内存碎片。显然，堆的效率比栈要低得多。
（6）存放内容不同。栈存放的内容，函数返回地址、相关参数、局部变量和寄存器内容等。当主函数调用另外一个函数的时候，要对当前函数执行断点进行保存，需要使用栈来实现，首先入栈的是主函数下一条语句的地址，即扩展指针寄存器的内容（EIP），然后是当前栈帧的底部地址，即扩展基址指针寄存器内容（EBP），再然后是被调函数的实参等，一般情况下是按照从右向左的顺序入栈，之后是被调函数的局部变量，注意静态变量是存放在数据段或者BSS段，是不入栈的。出栈的顺序正好相反，最终栈顶指向主函数下一条语句的地址，主程序又从该地址开始执行。堆，一般情况堆顶使用一个字节的空间来存放堆的大小，而堆中具体存放内容是由程序员来填充的。
从以上可以看到，堆和栈相比，由于大量malloc()/free()或new/delete的使用，容易造成大量的内存碎片，并且可能引发用户态和核心态的切换，效率较低。栈相比于堆，在程序中应用较为广泛，最常见的是函数的调用过程由栈来实现，函数返回地址、EBP、实参和局部变量都采用栈的方式存放。虽然栈有众多的好处，但是由于和堆相比不是那么灵活，有时候分配大量的内存空间，主要还是用堆。
无论是堆还是栈，在内存使用时都要防止非法越界，越界导致的非法内存访问可能会摧毁程序的堆、栈数据，轻则导致程序运行处于不确定状态，获取不到预期结果，重则导致程序异常崩溃，这些都是我们编程时与内存打交道时应该注意的问题。
2.数据结构中的堆与栈
数据结构中，堆与栈是两个常见的数据结构，理解二者的定义、用法与区别，能够利用堆与栈解决很多实际问题。
2.1 栈简介
栈是一种运算受限的线性表，其限制是指只仅允许在表的一端进行插入和删除操作，这一端被称为栈顶（Top），相对地，把另一端称为栈底（Bottom）。把新元素放到栈顶元素的上面，使之成为新的栈顶元素称作进栈、入栈或压栈（Push）；把栈顶元素删除，使其相邻的元素成为新的栈顶元素称作出栈或退栈（Pop）。这种受限的运算使栈拥有“先进后出”的特性（First In Last Out），简称 FILO。
栈分顺序栈和链式栈两种。栈是一种线性结构，所以可以使用数组或链表（单向链表、双向链表或循环链表）作为底层数据结构。使用数组实现的栈叫做顺序栈，使用链表实现的栈叫做链式栈，二者的区别是顺序栈中的元素地址连续，链式栈中的元素地址不连续。
栈的结构如下图所示：
栈的基本操作包括初始化、判断栈是否为空、入栈、出栈以及获取栈顶元素等。下面以顺序栈为例，使用 C++ 给出一个简单的实现。
1 #include
2 #include[span style="color: rgba(0, 0, 255, 1)">malloc.h>
3
4 #define DataType int
5 #define MAXSIZE 1024
6 struct SeqStack {
7 DataType data【MAXSIZE】;
8 int top;
9 };
10
11 //栈初始化,成功返回栈对象指针，失败返回空指针NULL
12 SeqStack initSeqStack() {
13 SeqStack s=(SeqStack)malloc(sizeof(SeqStack));
14 if(!s) {
15 printf("空间不足\n");
16 return NULL;
17 } else {
18 s->top = -1;
19 return s;
20 }
21 }
22
23 //判断栈是否为空
24 bool isEmptySeqStack(SeqStack s) {
25 if (s->top == -1)
26 return true;
27 else
28 return false;
29 }
30
31 //入栈，返回-1失败，0成功
32 int pushSeqStack(SeqStack s, DataType x) {
33 if(s->top == MAXSIZE-1)
34 {
35 return -1;//栈满不能入栈
36 } else {
37 s->top++;
38 s->data【s->top】 = x;
39 return 0;
40 }
41 }
42
43 //出栈，返回-1失败，0成功
44 int popSeqStack(SeqStack s, //代码效果参考：http://www.lyjsj.net.cn/wx/art_23747.html
DataType x) {45 if(isEmptySeqStack(s)) {
46 return -1;//栈空不能出栈
47 } else {
48 x = s->data【s->top】;
49 s->top--;
50 return 0;
51 }
52 }
53
54 //取栈顶元素，返回-1失败，0成功
55 int topSeqStack(SeqStack s,DataType x) {
56 if (isEmptySeqStack(s))
57 return -1; //栈空
58 else {
59 x=s->data【s->top】;
60 return 0;
61 }
62 }
63
64 //打印栈中元素
65 int printSeqStack(SeqStack s) {
66 int i;
67 printf("当前栈中的元素:\n");
68 for (i = s->top; i >= 0; i--)
69 printf("%4d",s->data【i】);
70 printf("\n");
71 return 0;
72 }
73
74 //test
75 int main() {
76 SeqStack seqStack=initSeqStack();
77 if(seqStack) {
78 //将4、5、7分别入栈
79 pushSeqStack(seqStack,4);
80 pushSeqStack(seqStack,5);
81 pushSeqStack(seqStack,7);
82
83 //打印栈内所有元素
84 printSeqStack(seqStack);
85
86 //获取栈顶元素
87 DataType x=0;
88 int ret=topSeqStack(seqStack,&x);
89 if(0==ret) {
90 printf("top element is %d\n",x);
91 }
92
93 //将栈顶元素出栈
94 ret=popSeqStack(seqStack,&x);
95 if(0==ret) {
96 printf("pop top element is %d\n",x);
97 }
98 }
99 return 0;
100 }
运行上面的程序，输出结果：
1 当前栈中的元素:
2 7 5 4
3 top element is 7
4 pop top element is 7
2.2 堆简介
2.2.1 堆的性质
堆是一种常用的树形结构，是一种特殊的完全二叉树，当且仅当满足所有节点的值总是不大于或不小于其父节点的值的完全二叉树被称之为堆。堆的这一特性称之为堆序性。
因此，在一个堆中，根节点是最大（或最小）节点。如果根节点最小，称之为小顶堆（或小根堆），如果根节点最大，称之为大顶堆（或大根堆）。堆的左右孩子没有大小的顺序。
下面是一个小顶堆示例：
2.2.2 堆的基本操作
（1）建立
以最小堆为例，如果以数组存储元素时，一个数组具有对应的树表示形式，但树并不满足堆的条件，需要重新排列元素，可以建立“堆化”的树。
（2）插入
将一个新元素插入到表尾，即数组末尾时，如果新构成的二叉树不满足堆的性质，需要重新排列元素，下图演示了插入15时，堆的调整。
（3）删除。
堆排序中，删除一个元素总是发生在堆顶，因为堆顶的元素是最小的（小顶堆中）。表中最后一个元素用来填补空缺位置，结果树被更新以满足堆条件。
2.2.3 堆操作实现
（1）插入代码实现
每次插入都是将新数据放在数组最后。可以发现从这个新数据的父节点到根节点必然为一个有序的数列，现在的任务是将这个新数据插入到这个有序数据中，这就类似于直接插入排序中将一个数据并入到有序区间中，这是节点“上浮”调整。不难写出插入一个新数据时堆的调整代码：
1 // 新加入i节点,其父节点为(i-1)/2
2 // 参数：a：数组，i：新插入元素在数组中的下标
3 void minHeapFixUp(int a【】, int i) {
4 int j, temp;
5 temp = a【i】;
6 j = (i-1)/2; //父节点
7 while (j >= 0 && i != 0) {
8 if (a【j】 <= temp)//如果父节点不大于新插入的元素，停止寻找
9 break;
10 a【i】=a【j】; //把较大的子节点往下移动,替换它的子节点
11 i = j;
12 j = (i-1)/2;
13 }
14 a【i】 = temp;
15 }
因此，插入数据到最小堆时：
1 // 在最小堆中加入新的数据data
2 // a：数组，index：插入的下标，
3 void minHeapAddNumber(int a【】, int index, int data) {
4 a【index】 = data;
5 minHeapFixUp(a, index);
6 }
（2）删除代码实现
按照堆删除的说明，堆中每次都只能删除第0个数据。为了便于重建堆，实际的操作是将数组最后一个数据与根节点交换，然后再从根节点开始进行一次从上向下的调整。
调整时先在左右儿子节点中找最小的，如果父节点不大于这个最小的子节点说明不需要调整了，反之将最小的子节点换到父节点的位置。此时父节点实际上并不需要换到最小子节点的位置，因为这不是父节点的最终位置。但逻辑上父节点替换了最小的子节点，然后再考虑父节点对后面的节点的影响。堆元素的删除导致的堆调整，其整个过程就是将根节点进行“下沉”处理。下面给出代码：
1 // a为数组，len为节点总数；从index节点开始调整，index从0开始计算index其子节点为 2index+1, 2*index+2；len/2-1为最后一个非叶子节点
2 void minHeapFixDown(int a【】,int len,<span style="col
