【AOJ ALDS1_9】B: Heaps - Maximum Heap

問題

ヒープの構築 | アルゴリズムとデータ構造 | Aizu Online Judge

方針

• 最大ヒープを作る問題
• 節点のキーが子のキーよりも大きいという条件を満たすものを最大ヒープという.
• ボトムアップに関数を適用することで最大ヒープに変換する.

コード

#include <iostream>

using namespace std;

#define H_MAX 500000
#define left(i) (i * 2)
#define right(i) (i * 2 + 1)

int h, A[H_MAX+1];

void maxHeapify(int i){
  int r = right(i);
  int l = left(i);
  int _max = i;
  
  if(l <= h && A[l] > A[_max]) _max =l;
  if(r <= h && A[r] > A[_max]) _max = r;

  if(_max != i){
    swap(A[i], A[_max]);
    maxHeapify(_max);
  }
}

int main(){
  cin >> h;
  for(int i = 1 ; i <= h ; i++){
    cin >> A[i];
  }

  for(int i = h/2 ; i >= 1 ; i--){
    maxHeapify(i);
  }

  for(int i = 1 ; i <= h ; i++){
    cout << " " << A[i];
  }

  cout << "\n";
}