数据结构——堆（介绍，堆的基本操作、堆排序）
我是一个计算机专业研0的学生卡蒙Camel🐫🐫🐫（刚保研）
记录每天学习过程（主要学习Java、python、人工智能），总结知识点（内容来自：自我总结+网上借鉴）
希望大家能一起发现问题和补充，也欢迎讨论👏👏👏
目录
- 堆
- 堆的介绍
- 堆存储
- 堆操作
- 堆插入
- 删除堆顶
- 自底向上堆化
- 自顶向下堆化
- 堆排序
- 1. 建堆
- 2. 排序
堆
堆的介绍
堆是一种特殊的树形数据结构，通常以完全二叉树的形式表示，并且满足堆属性。根据堆属性的不同，堆可以分为两种类型：
- 最大堆（Max Heap）：对于每个节点，它的值都大于或等于其子节点的值。因此，堆顶元素（根节点）总是最大的。
- 最小堆（Min Heap）：对于每个节点，它的值都小于或等于其子节点的值。因此，堆顶元素（根节点）总是最小的。
堆存储
- （二叉）堆可以用完全二叉树的形式进行存储。
- 树中任意节点
i，其左子节点序号为2*i，右子节点序号为2*i+1
堆操作
堆插入
- 将要插入的元素放到最后
- 从底向上，如果父结点比该元素小，则该节点和父结点交换，直到无法交换
删除堆顶
删除对顶元素是最大堆(最小堆)的最大值(最小值)，为了保持堆的性质，需要对堆的结构进行调整，我们将这个过程称之为"堆化"，有两种方法：
- 自底向上的堆化
- 自顶向下堆化
自底向上堆化
以大顶堆为例：
- 先删除堆顶元素(即数组中
index = 1的位置) - 比较根结点的左子节点和右子节点(
index = 2和3)，较大的元素放到根节点 - 此时又有空位，和步骤2一样，空位两个子节点较大的移动到空位，直到最底部
自顶向下堆化
- 我们将最后一个元素移动到堆顶。
- 不停与左右子节点的值进行比较，和较大的子节点交换位置，直到无法交换位置。
堆排序
堆排序分为两个步骤：
- 建堆
- 排序
1. 建堆
建堆需要对所有非叶节点的自顶向下堆化。
顺序是从index=n/2到index=1依次进行堆化
引用JavaGuide的图：
- 一开始没排序前的数组（n = 6， 所以要从索引为 3 到 1 的顺序进行堆化）：
- 对
index=3的节点进行堆化：
- 对
index=2的节点进行堆化
- 对index=1的节点进行堆化，堆化完成
2. 排序
我们在第一步已经建堆完毕，故堆顶元素就是最大值。所以我们重复取出堆顶元素，将这个最大的堆顶元素放至数组末尾，并对剩下的元素进行堆化即可。
- 取出堆顶元素并且堆化
- 一次取出堆顶并且优化
