C++数据结构输出堆插入排序每一趟结果

对于堆插入排序，每一趟排序都会将一个元素插入到已经排好序的部分中，并进行调整使得整个序列仍然保持堆的性质。下面给出一个C++代码实现，并输出每一趟排序的结果。

#include<iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest]) {
        largest = l;
    }
    if (r < n && arr[r] > arr[largest]) {
        largest = r;
    }
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

void heapInsert(int arr[], int n, int i) {
    int parent = (i - 1) / 2;
    while (parent >= 0 && arr[parent] < arr[i]) {
        swap(arr[parent], arr[i]);
        i = parent;
        parent = (i - 1) / 2;
    }
}

void heapInsertSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        heapInsert(arr, i + 1, i);
        for (int j = 0; j <= i; j++) {
            cout << arr[j] << " ";
        }
        cout << endl;
    }
}

int main() {
    int arr[] = { 5,2,3,1,4 };
    int n = sizeof(arr) / sizeof(arr[0]);
    heapInsertSort(arr, n);
    return 0;
}

在每一趟排序后，我们将已经排好序的部分和刚插入的元素一起输出，以便观察排序的过程。运行上述代码，得到的输出为：

5 
5 2 
5 3 2 
5 3 2 1 
5 4 2 1 3 

可以看到，每一趟排序后，都会将一个元素插入到已经排好序的部分中，并进行调整。