Heap Sort

// Heap 정렬(내림차순)
 
#include <stdio.h>
#define N 100
 
int n;
int data[N + 1];
int heap[N + 1];
 
void input()
{
    int i;
    scanf("%d", &n);
    for (i = 0; i<n; i++)
        scanf("%d", &data[i]);        // n개의 데이터 입력
}
 
void process()
{
    int i, x;
    int heap_cnt = 1;
 
    for (i = 0; i < n; i++)
    {
        heap[heap_cnt] = data[i];
        x = heap_cnt;
 
        while (x > 1)
        {
            if (heap[x / 2] > heap[x])    // 부모가 자식보다 클 때
            {
                int temp = heap[x / 2];
                heap[x / 2] = heap[x];
                heap[x] = temp;
                x = x / 2;            // 포지션을 부모 자리로 변경
            }
            else break;
        }
        heap_cnt++;
    }
 
    printf("Heap Tree : ");
    for (i = 1; i <= n; i++)
        printf("% d", heap[i]);
    printf("\n");
 
    printf("Output : ");
    for (i = 0; i<n; i++)
    {
        printf("%d ", heap[1]);        // 첫 번째 데이터
        heap_cnt--;                    // 제일 마지막 보다 한 칸 뒤의 위치를 가리키므로 -1
        heap[1] = heap[heap_cnt];    // 제일 첫 번째 칸에다 제일 마지막 자식을 저장
        heap[heap_cnt] = 0;            // 마지막 칸을 비움
        x = 1;                        // 위치는 1
        while (x * 2 < heap_cnt)        // 제일 마지막 자식 까지
        {
            if (heap[x] <= heap[2 * x] && (heap[x] <= heap[2 * x + 1] || x * 2 + 1 >= heap_cnt))        // 부모가 자식보다 작다면
                break;
            else if (heap[x * 2] <= heap[x] && (heap[x * 2] <= heap[x * 2 + 1] || x * 2 + 1 >= heap_cnt))                        // 왼쪽 자식이 제일 작을 때
            {
                int temp = heap[x];
                heap[x] = heap[x * 2];
                heap[x * 2] = temp;                // 제일 작은 자식을 부모자리로 교환
                x = x * 2;
            }
            else // 오른쪽 자식이 제일 작을 때
            {
                int temp = heap[x];
                heap[x] = heap[x * 2 + 1];
                heap[x * 2 + 1] = temp;
                x = x * 2 + 1;
            }
        }
 
    }
    printf("\n");
 
}
 
 
int main()
{
    input();
    process();
}

#include <stdio.h>
#define N 10
 
int heap[N + 1];
int sz = 1;
 
void push(int x)
{
    int i = sz++;
 
    while (i > 1)
    {
        // 부모 노드
        int p = i / 2;
 
        // 값의 역전 체크, 없으면 break
        if (heap[p] <= x) break;
 
        heap[i] = heap[p];
        i = p;
    }
    heap[i] = x;
}
 
int pop()
{
    // 최소 값
    int ret = heap[1];
 
    // 루트로 가져오는 값
    int x = heap[--sz];
 
    // 루트보다 작을 동안 값을 체크
    int i = 1;
    while (i * 2 < sz)
    {
        // 자식들을 비교
        int a = i * 2; 
        int b = i * 2 + 1;
        if (b < sz && heap[b] < heap[a]) a = b;
 
        // 더 이상 역전이 없다면 break
        if (heap[a] >= x) break;
 
        // 자식의 값을 저장
        heap[i] = heap[a];
        i = a;
    }
    heap[i] = x;
 
    return ret;
}