힙(Heap) 좀더 깔끔하게 짠 코드

힙에 대한 설명은 아래에서 참고한다.

https://www.crocus.co.kr/1184?category=150836

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

#include <iostream> #define MAX 101 #define SWAP(a,b){int t = a; a = b; b = t;}    // 최소 힙 int heap[MAX]; int hCnt;   void print() {     printf("heap :: [ ");     for (int i = 1; i <= hCnt; i++)         printf("%d ",heap[i]);     printf("]\n"); }   void push(int val) {     heap[++hCnt] = val;       int cur = hCnt;     int par = cur / 2;     while (cur > 1 && heap[cur] < heap[par]) {         SWAP(heap[cur], heap[par]);         cur = par;         par = cur / 2;     } }   int pop() {     if (hCnt == 0)         return -1;       int val = heap[1];     heap[1] = heap[hCnt--];       int cur = 1;     int next;       while (1) {         next = cur * 2;         if (next < hCnt && heap[next] > heap[next + 1]) // 무조건 right가 존재한다.(hCnt까지 힙이 존재하니)             next++; // 오른쪽 노드가 더 작으면 next를 오른쪽으로 만들어준다.         if (next > hCnt || heap[cur] < heap[next])             break; // 부모가 자식보다 작은값이면 break(최소 힙 유지)         SWAP(heap[cur], heap[next]);           cur = next;     }       return val; }   int main() {     print();     push(5);     print();     push(2);     print();     push(2);     print();     push(1);     print();     printf("팝 :: %d\n", pop());     print();     printf("팝 :: %d\n", pop());     print();     printf("팝 :: %d\n", pop());     print();     printf("팝 :: %d\n", pop());     print();     printf("팝 :: %d\n", pop());     print();     return 0; }   Colored by Color Scripter

cs