void heapSort(int *A, int n)       // 힙 정렬에 필요한 함수 호출
{
 int i, tmp;
 int static r = 0;
 buildHeap(A, n);
 for (i = n; i > 0; i--)          // 과정2-1) 정렬 시키기
 {
  tmp = A[i];
  A[i] = A[0];
  A[0] = tmp;
  printf("Make Sort[%d] : ", ++r);
  see(A, n);
  heapify(A, 0, i - 1);    // 과정2-2) 정렬 후 힙을 유지시키기
 }
}

void buildHeap(int *A, int n)       // 과정1-1) 힙이 되도록 알맞게 호출
{
 int i;
 int static k = 0;
 for (i = n / 2; i >= 0; i--){
  heapify(A, i,n);
  printf("Make Heap[%d] : ", ++k);
  see(A, n);
 }
}

void heapify(int *A, int k, int n)   // 과정1-2) 힙 만들기
{
 int tmp;
 int smaller;
 int Left = k * 2 + 1;
 int Right = k * 2 + 2;
 if (Right <= n)
 {
  if (A[Right] < A[Left])
   smaller = Right;
  else
   smaller = Left;
 }
 else if (Left <= n)
  smaller = Left;
 else
  return;
 if (A[k] > A[smaller])
 {
  tmp = A[k];
  A[k] = A[smaller];
  A[smaller] = tmp;
  heapify(A, smaller, n);
 }
}

void see(int *A, int n)            // 결과 호출
{
 int i;
 for (i = 0; i <= n; i++)
  printf("%d ", A[i]);
 printf("\n");
}