#include 
#define HEAPSIZE 100

int heap[100]; //heap[1] 이 루트 노드 
int n; //데이터 총 개수 

void insert_heap(int item)
{
   // n 개의 원소를 갖는 최대 히프에 item 을 삽입한다 
   int i;

   if (HEAPSIZE==n){
         printf("The heap is full \n");
         exit(1);
    }

    i=++n;
    while( (i!=1) && (item > heap[i/2]) ){
         heap[i]=heap[i/2]; 
         i/=2;
    }

    heap[i]=item;
}

int delete_heap()
{
    int parent,child;
    int item,temp;

    if ( n==0) {
         printf("heap is empty\n");
         exit(1);
    }

    item=heap[1];

    //heap 재 구성
    temp=heap[n--];
    parent=1;
    child=2;

    while ( child <= n){

         // 오른쪽 아들이 존재하고 , 오른쪽 아들이 왼쪽 아들보다 크면 오른쪽 아들로 변경
         if (child < n && heap[child] < heap[child+1]) child++; 

         // 마지막 데이터와 비교 후 크거나 같으면 탈출 
         if (temp >= heap[child]) break;

         // 아니면 자기위치로 부모를 내리고 
         heap[parent]=heap[child];
         
         parent=child;
         child*=2;
    }
    heap[parent]=temp;
    return item;
}

int main()
{
    insert_heap(3);
    insert_heap(5);
    insert_heap(4);
    printf("%d\n",delete_heap()); //3,5,4 중에 큰 데이터 5 가 출력 
    return 0;
}