【算法与数据结构】堆与栈的联系区别（多角度详解）

0 写在前面

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

1 程序内存分区中的堆与栈

1.1 栈简介

• 栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。

1.2 堆简介

• 堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。
• 研究算法空间复杂度 O(N) ： 最差情况下，即树退化为链表时，递归深度达到 NN，系统使用 O(N)O(N) 栈空间。

1.3 空间复杂度

• 我们刷算法题常说的空间复杂度就是程序执行的堆（参数赋值）和栈（函数执行）大小
• 一般堆的大小远大于栈的大小（毕竟函数每次执行完毕后会自动释放）
• 如果涉及到递归算法，那函数内部可能要执行多次函数，只有最后一次函数执行完毕才能开始释放空间，此时的空间复杂度 O(N) ： 对树结构进行遍历，最差情况下，即树退化为链表时，递归深度达到 N，系统使用 O(N)栈空间。

1.4 堆和栈区别

• 堆与栈实际上是操作系统对进程占用的内存空间的两种管理方式

• 管理方式不同。栈由操作系统自动分配释放，无需我们手动控制；堆的申请（指明大小）和释放工作由程序员控制，容易产生内存泄漏（是指程序中己动态分配的堆内存由于某种原因程序未释放或无法释放，造成系统内存的浪费，导致程序运行速度减慢甚至系统崩溃等严重后果）

• 空间大小不同。每个进程拥有的堆大小要远远大于栈大小。理论上，进程可申请的堆大小为虚拟内存大小，进程栈的大小 64bits 的 Windows 默认 1MB，64bits 的 Linux 默认 10MB

2 数据结构中的堆与栈

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

2.1 栈简介

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

2.2 堆简介

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

2.2.1 最小堆

• python自带最小堆函数（heapq）
• 每次pop()出来顶端最小值
  

2.2.2 show me code, no bb

import heapqlst = [1,2,3,5,1,5,8,9,6]'''
一秒变成堆
'''
heapq.heapify(lst)
[1, 1, 3, 5, 2, 5, 8, 9, 6]'''
最小的（顶端）再见，长度减一
'''
heapq.heappop(lst)
[1, 2, 3, 5, 6, 5, 8, 9]
'''
加入一个88，并重新建立堆，长度加一
'''
heapq.heappush(lst,88)
[1, 2, 3, 5, 6, 5, 8, 9,88]
'''
最小的滚蛋，新人进入，长度不变
'''
heapq.heapreplace(lst,99)
[2, 5, 3, 9, 6, 5, 8, 9, 99]'''
新人比最小的大，新人进入；若否，则不管：自带一步判断，长度不变
'''
heapq.heappushpop(lst,1)
[2, 5, 3, 9, 6, 5, 8, 9, 99]heapq.heappushpop(lst,66)
[3, 5, 5, 9, 6, 66, 8, 9, 99]'''
最大的n个是谁；
最小的n个是谁；
'''
print(heapq.nlargest(3,lst))
[99, 66, 9]
print(heapq.nsmallest(3,lst))
[3, 5, 5]'''
合并
'''
lst1 = [100,101]
lst2 = [3, 5, 5, 9, 6, 66, 8, 99]
lst = list(heapq.merge(lst1,lst2))
[3, 5, 5, 9, 6, 66, 8, 99, 100, 101]

• 代码全部亲自跑过，你懂的！😝

2.2.3 堆排序

• 堆的具体应用——堆排序
  • 堆排序（Heapsort）是堆的一个经典应用，有了上面对堆的了解，不难实现堆排序。由于堆也是用数组来存储的，故对数组进行堆化后，第一次将A[0]与A[n - 1]交换，再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换，再对A[0…n - 3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间，故操作完成后整个数组就有序了。
• leetcode很多和排序相关的题目：比如返回第几小、前几小，通过集合（存取去重数据）与最小堆（排序）的结合可以实现

写在最后

十年磨剑，与君共勉！
更多代码：gitee主页：https://gitee.com/GZHzzz
博客主页：CSDN：https://blog.csdn.net/gzhzzaa

• Fighting!😎

基于pytorch的经典模型：基于pytorch的典型智能体模型
强化学习经典论文：强化学习经典论文

while True:Go life

谢谢点赞交流！(❁´◡`❁)