编辑代码

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i;  // 初始化最大值的下标
    int left = 2 * i + 1;  // 左子节点的下标
    int right = 2 * i + 2;  // 右子节点的下标
    // 如果左子节点比根节点大，则更新最大值的下标
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    // 如果右子节点比当前最大值大，则更新最大值的下标
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    // 如果最大值的下标不是当前节点，则交换它们的位置并递归调整
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void buildHeap(int arr[], int n) {
    // 从最后一个非叶子节点开始向前遍历，对每个节点进行堆化操作
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

void heapSort(int arr[], int n) {
    buildHeap(arr, n);
    // 依次取出堆顶元素（最大值）并调整堆
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);  // 将堆顶元素（最大值）放到数组末尾
        heapify(arr, i, 0);  // 调整剩余元素为最大堆
    }
}

int main() {
    int arr[] = {52,9,76,16,25,18,4,98};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}