堆是一种特殊的树结构，它通常基于完全二叉树实现，并且满足大顶堆或小顶堆的性质。简单来说，堆是一个“特殊的完全二叉树”，其中每个父节点的值要么都大于等于子节点（大顶堆），要么都小于等于子节点（小顶堆）。这种结构让堆能够高效地获取最大值或最小值，因此在算法中应用广泛。

堆的存储方式¶

堆通常用数组来存储，因为完全二叉树的结构可以通过数组索引直接映射父子关系。假设数组的索引为 i（从0开始），那么：
- 左子节点的索引是 2*i + 1
- 右子节点的索引是 2*i + 2
- 父节点的索引是 (i - 1) // 2（向下取整）

例如，数组中索引为0的元素是根节点，它的左子节点是索引1，右子节点是索引2；索引1的父节点是索引0，左子节点是索引3，右子节点是索引4，以此类推。

大顶堆 vs 小顶堆¶

• 大顶堆：父节点的值 大于等于 所有子节点的值（根节点是最大值）。
• 小顶堆：父节点的值 小于等于 所有子节点的值（根节点是最小值）。

举个例子：
- 大顶堆数组：[9, 5, 7, 3, 6, 2, 4]（根节点9最大）
- 小顶堆数组：[3, 6, 5, 9, 7, 2, 4]（根节点3最小）

堆的基本操作¶

堆的核心操作包括 插入、删除、构建堆、获取堆顶，这些操作都依赖于堆的调整机制（上浮或下沉）。

1. 插入操作（上浮调整）¶

目的：向堆中添加一个元素，并保持堆的性质。
步骤：
1. 将新元素放在数组末尾（完全二叉树的最后一个空位）。
2. 从新元素的位置开始，与父节点比较：
- 如果是大顶堆且新元素 大于 父节点，交换两者位置；
- 如果是小顶堆且新元素 小于 父节点，交换两者位置。
3. 重复步骤2，直到父节点的性质满足或到达根节点。

示例（大顶堆插入元素10）：
原大顶堆数组：[9, 5, 7, 3, 6, 2, 4]（长度7）
- 插入10到末尾：[9, 5, 7, 3, 6, 2, 4, 10]
- 新元素在索引7，父节点是 (7-1)//2 = 3（值3），10 > 3，交换 → [9, 5, 7, 10, 6, 2, 4, 3]
- 新元素在索引3，父节点是 (3-1)//2 = 1（值5），10 > 5，交换 → [9, 10, 7, 5, 6, 2, 4, 3]
- 新元素在索引1，父节点是 (1-1)//2 = 0（值9），10 > 9，交换 → [10, 9, 7, 5, 6, 2, 4, 3]
- 到达根节点，插入完成，最终堆数组：[10, 9, 7, 5, 6, 2, 4, 3]

2. 删除操作（下沉调整）¶

目的：删除堆顶元素（大顶堆的最大值/小顶堆的最小值），并保持堆的性质。
步骤：
1. 将堆顶元素（数组索引0）与最后一个元素交换，然后删除最后一个元素。
2. 从新堆顶（原最后一个元素）的位置开始，与子节点比较：
- 如果是大顶堆，比较左右子节点，取 最大值，若堆顶元素 小于 最大值，交换位置；
- 如果是小顶堆，比较左右子节点，取 最小值，若堆顶元素 大于 最小值，交换位置。
3. 重复步骤2，直到堆顶元素的性质满足或到达叶子节点。

示例（大顶堆删除堆顶元素10）：
原大顶堆数组：[10, 9, 7, 5, 6, 2, 4]（长度7）
- 堆顶（10）与最后一个元素（4）交换：[4, 9, 7, 5, 6, 2, 10]，删除最后一个元素，数组变为 [4, 9, 7, 5, 6, 2]
- 新堆顶在索引0（值4），左右子节点：索引1（9）和索引2（7），取最大值9，4 < 9，交换 → [9, 4, 7, 5, 6, 2]
- 新堆顶在索引1（值4），左右子节点：索引3（5）和索引4（6），取最大值6，4 < 6，交换 → [9, 6, 7, 5, 4, 2]
- 新堆顶在索引4（值4），无有效子节点（超出数组长度），删除完成，最终堆数组：[9, 6, 7, 5, 4, 2]

3. 构建堆¶

目的：将一个无序数组转化为堆。
步骤：
1. 找到最后一个非叶子节点（索引 n//2 - 1，n 为数组长度）。
2. 从该节点开始，依次向上（即索引递减）对每个节点执行 下沉调整，直到根节点。

示例（将数组 [3, 1, 2, 6, 4, 5] 构建为大顶堆）：
- 数组长度 n=6，最后一个非叶子节点索引 6//2 - 1 = 2（值2）
- 处理索引2（值2）：左右子节点索引3（6）和4（4），最大值6，2 < 6，交换 → [3, 1, 6, 2, 4, 5]
- 处理索引1（值1）：左右子节点索引3（2）和4（4），最大值4，1 < 4，交换 → [3, 4, 6, 2, 1, 5]
- 处理索引0（值3）：左右子节点索引1（4）和2（6），最大值6，3 < 6，交换 → [6, 4, 3, 2, 1, 5]
- 调整完成，最终大顶堆数组：[6, 4, 3, 2, 1, 5]

4. 获取堆顶元素¶

直接返回数组索引0的元素（根节点），即大顶堆的最大值或小顶堆的最小值。

堆的应用¶

堆的高效性使其广泛用于：
- 优先队列：如任务调度（按优先级执行任务）、高频元素统计等。
- 堆排序：时间复杂度 O(n log n)，比冒泡排序、插入排序更高效。
- Top K问题：快速找到数组中前K大/小的元素。

总结¶

堆是一种基于完全二叉树的特殊结构，通过数组存储和上浮/下沉调整操作，能高效实现插入、删除、获取极值等功能。掌握堆的核心思想，对理解算法（如排序、优先队列）至关重要。初学者可以从简单的例子（如用数组模拟堆）入手，逐步熟悉插入和删除的调整过程。