最大堆【东北大学oj数据结构9-2】C++

满足“节点键值小于或等于其父键值”的最大堆条件的堆称为最大堆。 在最大堆中，最大的元素存储在根中，以某个节点为根的子树的节点的键值小于或等于该子树的根的键值。 请注意，只有父母和孩子之间有大小关系，兄弟姐妹之间没有限制。

创建一个程序，根据以下伪代码从给定数组构建最大堆。
maxHeapify (A, i) 将 A [i] 的值降低到最大堆叶，以便以节点 i 为根的子树是最大堆。 令 H 为堆大小。

 maxHeapify(A, i)
     l = left(i)
     r = right(i)
     if l ≤ H and A[l] > A[i]
         largest = l
     else 
         largest = i
     if r ≤ H and A[r] > A[largest]
        largest = r
     if largest ≠ i
        A[i] and A[largest] 
        maxHeapify(A, largest) 

下面的 buildMaxHeap (A) 通过自底向上应用 maxHeapify 将数组 A 转换为最大堆。 

buildMaxHeap(A)
   for i = H/2 downto 1
       maxHeapify(A, i) 

输入
输入的第一行给出了堆的大小 H。 然后，从节点号1到H依次给出代表堆中节点值的H个整数，用空格隔开。

输出
max-按照从节点号1到H的顺序在一行打印堆中节点的值。 在每个值之前输出一个空格字符。

约束
1 ≤ H ≤ 500,000
−2,000,000,000 ≤ 节点值 ≤ 2,000,000,000

输入样例

10
4 1 3 2 16 9 10 14 8 7

输出样例

16 14 10 8 7 9 3 2 4 1 

#include <iostream>
#include <vector>
 
using namespace std;
 
void maxHeapify(vector<int>& A,int i,int H)
{
    int left=2*i+1;
    int right=2*i+2;
    int largest=i;
    if(left<H&&A[left]>A[i])
        largest=left;
    if(right<H&&A[right]>A[largest])
        largest=right;
    if(largest!=i)
    {
        swap(A[i],A[largest]);
        maxHeapify(A,largest,H);
    }
}
void buildMaxHeap(vector<int>& A,int H)
{
    for(int i=H/2-1;i>=0;i--)
        maxHeapify(A,i,H);
}
 
int main() {
    int H;
    cin >> H;
    vector<int> A(H);
    for (int i = 0; i < H; ++i) {
        cin >> A[i];
    }
    buildMaxHeap(A,H);
    for (int i = 0; i <H; ++i) {
        cout<<A[i]<<" ";
    }
    cout << endl;
    return 0;
}