#include <iostream>

using namespace std;

//小顶堆&大顶堆

int sz[1000]={0,60,30,15,27,45,32,16,90,40,20,10,12};

//10 20 12 27 30 15 16 90 40 60 45 32 小顶

//90 60 32 40 45 15 16 27 20 30 10 12 大顶

int n=12;

void put(int x){

   //放置x点

   int k=x*2;

   if(k+1<=n&&sz[k+1]<sz[k]) k++;

   if(sz[x]>sz[k]){

       swap(sz[x],sz[k]);

       if(k*2<=n) put(k);

   }

   //跟左右子节点比较

   //如果交换了，看新的位置是否需要放置【递归】

}

void put2(int x){

   int k=x*2;

   if(k+1<=n&&sz[k+1]>sz[k]) k++;

   if(sz[x]<sz[k]){

       swap(sz[x],sz[k]);

       if(k*2<=n) put2(k);

   }

}

int main(){

   //从倒数第一个有子节点的节点开始，向根节点遍历

   for(int i=n/2;i>=1;i--){

       //将当前节点放置到正确的位置

       put(i);

   }

   for(int i=1;i<=n;i++) cout<<sz[i]<<" ";cout<<endl;

   for(int i=n/2;i>=1;i--){

       put2(i);

   }

   for(int i=1;i<=n;i++) cout<<sz[i]<<" ";

   return 0;

}