最大堆【东北大学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;
}