Heap Sort

힙 정렬은 MAX HEAP 과 MIN HEAP으로 나뉘어져있다.

이진 탐색 트리의 특징을 가지며, 부모 노드는 자식 노드 인덱스의 나누기 2이다.

주의할 점은 인덱스는 1부터 시작해야한다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86

#include <stdio.h> #define MAX_HEAP    (30000) int N; int heap[MAX_HEAP + 1]; int lastnode = 0;   int Heap_Push(int d)   {     int c, p, temp;     if (lastnode == MAX_HEAP) return -1;     heap[++lastnode] = d;     c = lastnode, p = c / 2;     while (p > 0) {         if (heap[c] > heap[p]) {             temp = heap[c];             heap[c] = heap[p];             heap[p] = temp;             c = p; p = c / 2;         }         else break;     }       return 1; }   int Heap_Pop(int *d)   {     int c, l, r, p, temp;     if (lastnode == 0) return -1;     *d = heap[1];     heap[1] = heap[lastnode--];     p = 1; l = 2; r = 3;     while (l <= lastnode) {         if (l == lastnode) c = l;         else if (heap[l] > heap[r]) c = l;         else c = r;         if (heap[c] > heap[p]) {             temp = heap[c];             heap[c] = heap[p];             heap[p] = temp;             p = c; l = p * 2, r = p * 2 + 1;         }         else break;     }       return 1;   }     int main(void)   {       int i, d;     scanf("%d", &N);     for (i = 0; i < N; i++)     {         scanf("%d", &d);         Heap_Push(d);     }     for (i = N; i >= 1; i--)     {         Heap_Pop(&d);         heap[i] = d;     }       for (i = 1; i <= N; i++)     {         printf("%d ", heap[i]);       }     return 0;   }