#include <stdio.h>

#define INT_MAX 13

void upheap(int a[], int k)
{
	int v;
	v = a[k];  /* v는 k번 노드의 키값을 가진다 */
	a[0] = INT_MAX;
	while(a[k/2] <= v){  /* 부모의 카기 v보다 작으면 삽입한다 */
		a[k] = a[k/2];
		k /= 2;
	}
	a[k] = v;  /* 제자리에 v를 놓는다 */
}

void downheap(int a[], int n, int k)
{
	int i, v;
	v = a[k];
	while(k <= n/2){  /* k가 내부 노드인 경우에 한해서 */
		i = k<<1;  /* i는 왼쪽 자식 번호 */
		if(i < n && a[i] < a[i+1]) i++;  /* 왼쪽과 오른쪽 자식 중에 큰 것을 선택 */
		if(v >= a[i]) break;  /* 힙 조건을 만족하면 중단 */
		a[k] = a[i];  /* 힙 조건을 만족하지 않으면 삽입 */
		k = i;
	}
	a[k] = v;  /* k는 v가 들어가야 할 자리이다 */


}

void insert(int a[], int *n, int v)
{
	a[++(*n)] = v;  /* 힙의 노드수를 증가하고 v를 추가 */
	upheap(a, *n);  /* unheap 동작 수행 */

}

int extract(int a[], int *n)  /* remove 기능을 한다 */
{

	int v = a[1];  /* a[i]는 뿌리이므로 힙의 최대값 */
	a[1] = a[(*n)--];  /* 뿌리에 힙의 말단 노드를 넣고 노드수는 감소한다 */
	downheap(a, *n, 1);  /* 뿌리의 노드를 힙의 조건에 맞게 하강 */
	return v;  /* 원래 뿌리의 값(힙의 최대값)을 리턴 */
}

void heap_sort(int a[], int n)  /* 하향식 힙 생성을 이용한 힙 정렬 */
{
	int i;
	int hn = 0;  /* hn은 노드수이다. n은 배열의 크기 */
	
	for(i=1; i<=n; i++)  /* 배열의 값을 차례로 힙에 삽입 */
		insert(a, &hn, a[i]);  /* a 배열을 힙으로 사용함 */

	for(i=hn; i>=1; i--){  /* 힙의 최대값을 꺼내어 역순으로 저장한다 */
		a[i] = extract(a, &hn);
	}
}

/*****************************************************************************
*                                                                            *
*  --------------------------------- main ---------------------------------  *
*                                                                            *
*****************************************************************************/

void main(void)
{
	int a[13] =
	{5, 4, 3, 2, 1, 6, 7, 8, 9, 10, 12, 11};
	int i;
	
    heap_sort(a, 13);

	for(i=0; i<13; i++)
		printf("%3d", a[i]);
	
}