数据结构——堆（介绍，堆的基本操作、堆排序）

我是一个计算机专业研0的学生卡蒙Camel🐫🐫🐫（刚保研）
记录每天学习过程（主要学习Java、python、人工智能），总结知识点（内容来自：自我总结+网上借鉴）
希望大家能一起发现问题和补充，也欢迎讨论👏👏👏

堆

堆的介绍

堆是一种特殊的树形数据结构，通常以完全二叉树的形式表示，并且满足堆属性。根据堆属性的不同，堆可以分为两种类型：

• 最大堆（Max Heap）：对于每个节点，它的值都大于或等于其子节点的值。因此，堆顶元素（根节点）总是最大的。
• 最小堆（Min Heap）：对于每个节点，它的值都小于或等于其子节点的值。因此，堆顶元素（根节点）总是最小的。

堆存储

• （二叉）堆可以用完全二叉树的形式进行存储。
• 树中任意节点 i，其左子节点序号为 2*i，右子节点序号为 2*i+1

堆操作

堆插入

1. 将要插入的元素放到最后
2. 从底向上，如果父结点比该元素小，则该节点和父结点交换，直到无法交换

删除堆顶

删除对顶元素是最大堆(最小堆)的最大值(最小值)，为了保持堆的性质，需要对堆的结构进行调整，我们将这个过程称之为"堆化"，有两种方法：

1. 自底向上的堆化
2. 自顶向下堆化

自底向上堆化

以大顶堆为例：

1. 先删除堆顶元素(即数组中index = 1的位置)
2. 比较根结点的左子节点和右子节点(index = 2和3)，较大的元素放到根节点
3. 此时又有空位，和步骤2一样，空位两个子节点较大的移动到空位，直到最底部

自顶向下堆化

1. 我们将最后一个元素移动到堆顶。
2. 不停与左右子节点的值进行比较，和较大的子节点交换位置，直到无法交换位置。

堆排序

堆排序分为两个步骤：

1. 建堆
2. 排序

1. 建堆

建堆需要对所有非叶节点的自顶向下堆化。

顺序是从index=n/2到index=1依次进行堆化

引用JavaGuide的图：

1. 一开始没排序前的数组（n = 6， 所以要从索引为 3 到 1 的顺序进行堆化）：

2. 对index=3的节点进行堆化：

3. 对index=2的节点进行堆化

4. 对index=1的节点进行堆化，堆化完成

2. 排序

我们在第一步已经建堆完毕，故堆顶元素就是最大值。所以我们重复取出堆顶元素，将这个最大的堆顶元素放至数组末尾，并对剩下的元素进行堆化即可。

1. 取出堆顶元素并且堆化

2. 一次取出堆顶并且优化