一文读懂堆与栈的区别 |
您所在的位置：网站首页 › cpu4570和4590有什么区别 › 一文读懂堆与栈的区别 |
一文读懂堆与栈的区别
|
大咖好呀，我是恋喵大鲤鱼。 鄙人开源书籍 《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); couttop]; 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] (len/2-1)) return; int tmp=a[index]; lastIndex=index; // 当下沉到叶子节点时，就不用调整了。 while(index |
堆的存储一般都用数组来存储堆，i节点的父节点下标就为
(
i
–
1
)
/
2
(i – 1) / 2
(i–1)/2。它的左右子节点下标分别为
2
∗
i
+
1
2 * i + 1
2∗i+1 和
2
∗
i
+
2
2 * i + 2
2∗i+2。如第0个节点左右子节点下标分别为1和2。 
【本文地址】
今日新闻 |
推荐新闻 |