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

堆排序原理

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

C++实现

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

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

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实现：

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. 逻辑上的合理性

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

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