堆排序是一种利用堆这种数据结构所设计的排序算法，它是基于选择排序的一种改进。堆排序分为两个步骤：建堆和排序。

### 堆排序原理
- **建堆**：首先将待排序的序列构建成一个大顶堆（或小顶堆），此时堆顶元素（数组的第一个元素）是整个序列的最大值（或最小值）。
- **排序**：将堆顶元素与末尾元素交换，然后将剩余的序列重新调整为堆，重复此过程，直到整个序列有序。

### C++实现
下面是一个使用C++实现的堆排序算法的示例代码：

```cpp
#include <iostream>
using namespace std;

// 调整堆，使其满足堆的性质
void adjustHeap(int arr[], int i, int size) {
    int temp = arr[i]; // 保存当前元素的值
    for (int k = 2 * i + 1; k < size; k = 2 * k + 1) { // 从i节点的左子节点开始
        if (k + 1 < size && arr[k] < arr[k + 1]) { // 如果左子节点小于右子节点，k指向右子节点
            k++;
        }
        if (arr[k] > temp) { // 如果子节点大于父节点，将子节点值赋给父节点
            arr[i] = arr[k];
            i = k;
        } else {
            break;
        }
    }
    arr[i] = temp; // 将temp值放到最终的位置
}

// 建立堆
void buildHeap(int arr[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) { // 从最后一个非叶子节点开始调整
        adjustHeap(arr, i, size);
    }
}

// 堆排序
void heapSort(int arr[], int size) {
    buildHeap(arr, size); // 建立大顶堆
    for (int i = size - 1; i > 0; i--) {
        swap(arr[i], arr[0]); // 将堆顶元素与最后一个元素交换
        adjustHeap(arr, 0, i); // 重新调整堆
    }
}

int main() {
    int arr[] = {4, 6, 8, 5, 9};
    int size = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    heapSort(arr, size);

    cout << "Sorted array: ";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}
```

### 代码说明
- `adjustHeap` 函数用于调整堆，使其满足堆的性质。它从指定的节点开始，向下调整，直到满足堆的性质。
- `buildHeap` 函数用于建立初始的堆。它从最后一个非叶子节点开始，依次向上调整每个节点。
- `heapSort` 函数是堆排序的主函数，它首先建立初始堆，然后通过交换堆顶元素和最后一个元素，并重新调整堆，直到整个数组有序。

### 时间复杂度
- 建堆的时间复杂度是 \(O(n)\)。
- 排序的时间复杂度是 \(O(n \log n)\)。
- 因此，堆排序的总时间复杂度是 \(O(n \log n)\)。

堆排序是一种不稳定的排序算法，但它具有较好的时间复杂度和空间复杂度（空间复杂度为 \(O(1)\)），因此在很多实际应用中被广泛使用.

将 `adjustHeap` 函数从迭代形式改写为递归形式，主要思路是将循环逻辑转换为递归调用。递归版本的核心在于每次处理一个节点后，递归地调整其子节点。以下是递归版本的实现：

```cpp
void adjustHeapRecursive(int arr[], int i, int size) {
    int left = 2 * i + 1; // 左子节点的索引
    int right = 2 * i + 2; // 右子节点的索引
    int largest = i; // 假设当前节点是最大的

    // 如果左子节点存在且大于当前节点，则更新 largest
    if (left < size && arr[left] > arr[largest]) {
        largest = left;
    }

    // 如果右子节点存在且大于当前最大节点，则更新 largest
    if (right < size && arr[right] > arr[largest]) {
        largest = right;
    }

    // 如果最大的节点不是当前节点，交换它们并递归调整
    if (largest != i) {
        swap(arr[i], arr[largest]);
        adjustHeapRecursive(arr, largest, size); // 递归调整交换后的子树
    }
}
```

### 代码解释
- **参数说明**：
  - `arr[]`：待调整的数组。
  - `i`：当前需要调整的节点的索引。
  - `size`：数组的大小。

- **逻辑流程**：
  1. **计算子节点索引**：计算当前节点的左子节点和右子节点的索引。
  2. **确定最大节点**：比较当前节点、左子节点和右子节点，确定最大值的索引。
  3. **交换节点**：如果最大值的索引不是当前节点的索引，说明需要调整，将当前节点与最大值节点交换。
  4. **递归调整**：交换后，递归地调整交换后的子树，以确保子树仍然满足堆的性质.

### 使用递归的优势
- **代码简洁**：递归版本的代码通常比迭代版本更简洁，逻辑更直观。
- **易于理解**：对于熟悉递归的程序员来说，递归版本的代码更容易理解和调试。

### 注意事项
- **递归深度**：对于非常大的数组，递归可能会导致栈溢出。因此，在实际应用中，对于大规模数据，迭代版本可能更安全.
- **性能开销**：递归调用会增加函数调用的开销，因此在性能要求较高的场景中，迭代版本可能更优.

递归版本的 `adjustHeap` 函数在逻辑上与迭代版本等价，但在实现方式上更加直观和简洁.

给出堆排序算法的python实现

堆排序是一种利用堆这种数据结构所设计的排序算法。它是一种选择排序，分为两个步骤：建立堆和堆调整。

以下是堆排序算法的Python实现：

```python
def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    # 建立最大堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 一个一个从堆顶取出元素
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

# 示例
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("排序后的数组是:", arr)
```

在这个实现中，`heapify` 函数用于维护堆的性质，`heap_sort` 函数则用于执行整个堆排序过程。首先，通过从最后一个非叶子节点开始向上调整，建立一个最大堆。然后，将堆顶元素（最大值）与最后一个元素交换，并调整剩余的堆，直到整个数组被排序。

在堆排序算法中，`k = 2 * k + 1` 这个表达式用于在调整堆的过程中找到当前节点的左子节点。具体来说，这个表达式的作用是遍历当前节点的所有子节点，以确保堆的性质得到满足。以下是详细的解释：

### 堆的结构
- **堆**是一种完全二叉树，通常用数组来表示。对于数组中的任意节点 `i`：
  - 左子节点的索引为 `2 * i + 1`。
  - 右子节点的索引为 `2 * i + 2`。

### 调整堆的目的
- 在调整堆的过程中，我们需要确保当前节点（父节点）大于其子节点（对于大顶堆）。如果当前节点小于其子节点，我们需要将当前节点与子节点中最大的一个交换，然后继续调整交换后的子节点，以确保整个子树满足堆的性质。

### `k = 2 * k + 1` 的作用
- **初始设置**：在循环开始时，`k` 被设置为 `2 * i + 1`，即当前节点的左子节点的索引。
- **循环条件**：只要 `k < size`，说明当前节点还有子节点需要检查。
- **更新 `k`**：在循环中，如果当前节点的左子节点小于右子节点，`k` 会被更新为右子节点的索引。如果需要交换当前节点和子节点，`k` 会被更新为 `2 * k + 1`，即交换后的新节点的左子节点的索引。这样可以继续检查和调整新的子节点，确保整个子树满足堆的性质。

### 代码逻辑
- 在 `adjustHeap` 函数中，`k = 2 * k + 1` 是用来在交换节点后，继续向下调整堆的。如果当前节点与子节点交换后，新的子节点可能仍然不满足堆的性质，因此需要继续向下调整，直到整个子树都满足堆的性质。

通过这种方式，`adjustHeap` 函数能够有效地将当前节点下沉到合适的位置，确保堆的性质在整个数组中得到满足。

为什么build堆的时候要从最后一个非叶子节点开始调整

在构建堆的过程中，从最后一个非叶子节点开始调整的原因主要有以下几点：

### 1. **叶子节点的性质**
- **叶子节点的定义**：在完全二叉树中，叶子节点是没有子节点的节点。对于一个数组表示的完全二叉树，叶子节点自然满足堆的性质，因为它们没有子节点可以违反堆的性质。
- **无需调整**：由于叶子节点没有子节点，它们天然满足堆的性质（即每个节点都大于或等于其子节点）。因此，不需要对叶子节点进行任何调整。

### 2. **从下到上的调整策略**
- **自下而上的调整**：从最后一个非叶子节点开始调整，可以确保在调整每个节点时，其子树已经满足堆的性质。这样可以避免重复调整子树。
- **逐步修复**：从最后一个非叶子节点开始，逐步向上调整，可以看作是一个“从下往上”的修复过程。这种方法确保了在调整当前节点时，其子树已经是一个合法的堆。

### 3. **效率和时间复杂度**
- **时间复杂度优化**：虽然每次调整操作的时间复杂度为 \(O(\log n)\)，但由于从最后一个非叶子节点开始调整，整体的时间复杂度为 \(O(n)\)。这是因为每个节点的调整次数与其在树中的深度有关，而树的深度逐层递减。
- **避免重复工作**：如果从根节点开始调整，可能会导致对已经满足堆性质的子树进行不必要的调整，从而增加计算量。

### 4. **逻辑上的合理性**
- **确保子树合法性**：在调整当前节点时，确保其子树已经是一个合法的堆，可以简化调整过程。如果子树不满足堆的性质，调整过程会变得复杂。
- **逐步构建合法堆**：从最后一个非叶子节点开始，逐步向上构建合法的堆，可以确保在每一步中，当前节点及其子树都满足堆的性质。

综上所述，从最后一个非叶子节点开始调整堆是一种高效且合理的策略，能够确保在构建过程中逐步修复和构建合法的堆结构，从而提高整个建堆过程的效率和正确性.