堆排序算法的单元测试：确保堆排序算法的正确性，构建可靠的算法基础

# 1. 堆排序算法简介**

堆排序算法是一种基于堆数据结构的排序算法。它利用堆的性质，将待排序的元素组织成一个最大堆，然后依次取出堆顶元素，并重新调整堆的结构，最终得到一个有序序列。堆排序算法的时间复杂度为 O(n log n)，空间复杂度为 O(1)，具有较高的效率和稳定性。

# 2. 堆排序算法的理论基础

### 2.1 堆的数据结构和性质

#### 2.1.1 堆的定义和基本操作

**定义：**堆是一种完全二叉树，其中每个节点的值都大于或等于其子节点的值。

**基本操作：**

* **插入（Insert）：**将一个元素插入堆中，保持堆的性质。
* **删除（Delete）：**从堆中删除堆顶元素，并保持堆的性质。
* **调整（Adjust）：**当堆中某个节点的子节点违反堆的性质时，调整该节点及其子节点，以恢复堆的性质。

#### 2.1.2 堆的性质和排序原理

**性质：**

* **完全二叉树：**堆是一棵完全二叉树，除了最后一层可能不全外，其他层都填满。
* **最大堆：**每个节点的值都大于或等于其子节点的值。
* **最小堆：**每个节点的值都小于或等于其子节点的值。

**排序原理：**

堆排序算法利用堆的性质进行排序。通过构建一个最大堆，堆顶元素就是最大值。然后，将堆顶元素出堆，并调整堆，使堆顶元素再次成为最大值。重复此过程，直到堆中只剩下一个元素，即可得到一个有序序列。

### 2.2 堆排序算法的流程

#### 2.2.1 构建最大堆

**步骤：**

1. 将输入序列视为一个完全二叉树。
2. 从最后一个非叶子节点开始，逐层向上调整堆，确保每个节点都满足堆的性质。

**代码块：**

def build_max_heap(arr):
    """构建最大堆。

    参数：
        arr：输入序列。

    返回：
        无。
    """
    for i in range(len(arr) // 2 - 1, -1, -1):
        adjust_max_heap(arr, i, len(arr))

**逻辑分析：**

* 循环从最后一个非叶子节点开始，逐层向上调整堆。
* 调用 `adjust_max_heap` 函数调整每个节点及其子节点，确保堆的性质。

#### 2.2.2 堆顶元素出堆和堆的调整

**步骤：**

1. 将堆顶元素与最后一个元素交换。
2. 删除最后一个元素。
3. 调整堆，使堆顶元素再次成为最大值。

**代码块：**

def heap_sort(arr):
    """堆排序。

    参数：
        arr：输入序列。

    返回：
        无。
    """
    build_max_heap(arr)

    for i in range(len(arr) - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        adjust_max_heap(arr, 0, i)

**逻辑分析：**

* 调用 `build_max_heap` 函数构建最大堆。
* 循环从堆顶元素开始，逐个出堆并调整堆。
* 交换堆顶元素与最后一个元素，删除最后一个元素。
* 调用 `adjust_max_heap` 函数调整堆，使堆顶元素再次成为最大值。

# 3.1 Python中的堆排序实现

#### 3.1.1 使用列表表示堆

在Python中，我们可以使用列表来表示堆。列表中的每个元素都代表堆中的一个节点，根节点位于列表的第一个元素。为了保持堆的性质，我们需要使用以下规则来组织列表：

- **左子节点：**位于父节点索引的2倍