满足“节点键值小于或等于其父键值”的最大堆条件的堆称为最大堆。 在最大堆中，最大的元素存储在根中，以某个节点为根的子树的节点的键值小于或等于该子树的根的键值。 请注意，只有父母和孩子之间有大小关系，兄弟姐妹之间没有限制。
创建一个程序，根据以下伪代码从给定数组构建最大堆。
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;
}