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 | // 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(); } | cs |
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 | #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; } | cs |