堆排序【东北大学oj数据结构9-4】C++

堆排序是一种基于堆的数据结构的排序，是一种快速排序算法，可以在输入数组中实现排序处理（内存高效）。 堆排序可以实现如下：

maxHeapify(A, i)
    l = left(i)
    r = right(i)
    // select the node which has the maximum value
    if l ≤ heapSize and A[l] > A[i]
        largest = l
    else 
        largest = i
    if r ≤ heapSize and A[r] > A[largest]
        largest = r
        
    if largest ≠ i　
        swap A[i] and A[largest]
        maxHeapify(A, largest) 

heapSort(A):
    // buildMaxHeap
    for i = N/2 downto 1:
        maxHeapify(A, i)
    // sort
    heapSize ← N
    while heapSize ≥ 2:
        swap(A[1], A[heapSize])
        heapSize--
        maxHeapify(A, 1)

另一方面，堆排序频繁地交换远处的元素，导致对非连续元素的大量随机访问。

现在给你 N 个元素的序列 A，你要找到它的一个排列，使得它是一个最大堆，且当把它变成排好序的序列时，伪代码第25行的maxHeapify中交换的总次数尽可能最大。

输入

第一行给出了整数 N，它表示序列的长度。
在第二行，给出了 N 个整数，用空格分隔。
1 ≤ N ≤ 200000
0 ≤ A ≤ 1000000000
A的所有元素都不同

输出

在一行输出满足条件的序列。 请输出以一个空格分隔的序列的连续元素。

对于一个输入，这个问题有多个答案。 所有满足条件的输出都是正确的。

输入样例

8
1 2 3 5 9 12 15 23

输出样例

23 9 15 2 5 3 12 1 

代码

下面的代码不完全按照题干伪代码排序

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// Function to reconstruct the max heap
void buildMaxHeap(vector<int>& A) {
    int n = A.size();
    for (int i = n / 2 - 1; i >= 0; i--) {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        if (l < n && A[l] > A[largest]) {
            largest = l;
        }
        if (r < n && A[r] > A[largest]) {
             largest = r;
        }
        if (largest != i) {
            swap(A[i], A[largest]);
            i=largest+1;//restart from the updated node to make sure all changes reflected
             if (i<=n/2-1){
                i--;
            }
             else {
                 i=-1;
             }
        }
    }
}
 
 
int main() {
    int n;
    cin >> n;
 
    vector<int> A(n);
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
 
    sort(A.begin(),A.end(),greater<int>());
 
    buildMaxHeap(A);
 
    for (int i = 0; i < n; i++) {
        cout << A[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;
 
    return 0;
}