10_heap.c

Download
c 471 lines 12.4 KB 
  1/*
  2 * ํž™ (Heap)
  3 * Min Heap, Max Heap, Heap Sort, Priority Queue
  4 *
  5 * ์™„์ „ ์ด์ง„ ํŠธ๋ฆฌ ๊ธฐ๋ฐ˜์˜ ์šฐ์„ ์ˆœ์œ„ ์ž๋ฃŒ๊ตฌ์กฐ์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <stdbool.h>
 11
 12/* =============================================================================
 13 * 1. ์ตœ์†Œ ํž™ (Min Heap)
 14 * ============================================================================= */
 15
 16typedef struct {
 17    int* data;
 18    int size;
 19    int capacity;
 20} MinHeap;
 21
 22MinHeap* minheap_create(int capacity) {
 23    MinHeap* heap = malloc(sizeof(MinHeap));
 24    heap->data = malloc(capacity * sizeof(int));
 25    heap->size = 0;
 26    heap->capacity = capacity;
 27    return heap;
 28}
 29
 30void minheap_free(MinHeap* heap) {
 31    free(heap->data);
 32    free(heap);
 33}
 34
 35void minheap_swap(int* a, int* b) {
 36    int temp = *a;
 37    *a = *b;
 38    *b = temp;
 39}
 40
 41void minheap_sift_up(MinHeap* heap, int idx) {
 42    while (idx > 0) {
 43        int parent = (idx - 1) / 2;
 44        if (heap->data[parent] <= heap->data[idx])
 45            break;
 46        minheap_swap(&heap->data[parent], &heap->data[idx]);
 47        idx = parent;
 48    }
 49}
 50
 51void minheap_sift_down(MinHeap* heap, int idx) {
 52    while (2 * idx + 1 < heap->size) {
 53        int smallest = idx;
 54        int left = 2 * idx + 1;
 55        int right = 2 * idx + 2;
 56
 57        if (left < heap->size && heap->data[left] < heap->data[smallest])
 58            smallest = left;
 59        if (right < heap->size && heap->data[right] < heap->data[smallest])
 60            smallest = right;
 61
 62        if (smallest == idx) break;
 63
 64        minheap_swap(&heap->data[idx], &heap->data[smallest]);
 65        idx = smallest;
 66    }
 67}
 68
 69void minheap_push(MinHeap* heap, int val) {
 70    if (heap->size >= heap->capacity) return;
 71    heap->data[heap->size] = val;
 72    minheap_sift_up(heap, heap->size);
 73    heap->size++;
 74}
 75
 76int minheap_pop(MinHeap* heap) {
 77    if (heap->size == 0) return -1;
 78
 79    int min = heap->data[0];
 80    heap->data[0] = heap->data[--heap->size];
 81    minheap_sift_down(heap, 0);
 82    return min;
 83}
 84
 85int minheap_peek(MinHeap* heap) {
 86    return heap->size > 0 ? heap->data[0] : -1;
 87}
 88
 89/* =============================================================================
 90 * 2. ์ตœ๋Œ€ ํž™ (Max Heap)
 91 * ============================================================================= */
 92
 93typedef struct {
 94    int* data;
 95    int size;
 96    int capacity;
 97} MaxHeap;
 98
 99MaxHeap* maxheap_create(int capacity) {
100    MaxHeap* heap = malloc(sizeof(MaxHeap));
101    heap->data = malloc(capacity * sizeof(int));
102    heap->size = 0;
103    heap->capacity = capacity;
104    return heap;
105}
106
107void maxheap_free(MaxHeap* heap) {
108    free(heap->data);
109    free(heap);
110}
111
112void maxheap_sift_up(MaxHeap* heap, int idx) {
113    while (idx > 0) {
114        int parent = (idx - 1) / 2;
115        if (heap->data[parent] >= heap->data[idx])
116            break;
117        minheap_swap(&heap->data[parent], &heap->data[idx]);
118        idx = parent;
119    }
120}
121
122void maxheap_sift_down(MaxHeap* heap, int idx) {
123    while (2 * idx + 1 < heap->size) {
124        int largest = idx;
125        int left = 2 * idx + 1;
126        int right = 2 * idx + 2;
127
128        if (left < heap->size && heap->data[left] > heap->data[largest])
129            largest = left;
130        if (right < heap->size && heap->data[right] > heap->data[largest])
131            largest = right;
132
133        if (largest == idx) break;
134
135        minheap_swap(&heap->data[idx], &heap->data[largest]);
136        idx = largest;
137    }
138}
139
140void maxheap_push(MaxHeap* heap, int val) {
141    if (heap->size >= heap->capacity) return;
142    heap->data[heap->size] = val;
143    maxheap_sift_up(heap, heap->size);
144    heap->size++;
145}
146
147int maxheap_pop(MaxHeap* heap) {
148    if (heap->size == 0) return -1;
149
150    int max = heap->data[0];
151    heap->data[0] = heap->data[--heap->size];
152    maxheap_sift_down(heap, 0);
153    return max;
154}
155
156/* =============================================================================
157 * 3. ํž™ ์ •๋ ฌ
158 * ============================================================================= */
159
160void heapify(int arr[], int n, int i) {
161    int largest = i;
162    int left = 2 * i + 1;
163    int right = 2 * i + 2;
164
165    if (left < n && arr[left] > arr[largest])
166        largest = left;
167    if (right < n && arr[right] > arr[largest])
168        largest = right;
169
170    if (largest != i) {
171        minheap_swap(&arr[i], &arr[largest]);
172        heapify(arr, n, largest);
173    }
174}
175
176void heap_sort(int arr[], int n) {
177    /* ์ตœ๋Œ€ ํž™ ๊ตฌ์„ฑ */
178    for (int i = n / 2 - 1; i >= 0; i--) {
179        heapify(arr, n, i);
180    }
181
182    /* ์ •๋ ฌ */
183    for (int i = n - 1; i > 0; i--) {
184        minheap_swap(&arr[0], &arr[i]);
185        heapify(arr, i, 0);
186    }
187}
188
189/* =============================================================================
190 * 4. K๋ฒˆ์งธ ์ตœ์†Œ/์ตœ๋Œ€ ์›์†Œ
191 * ============================================================================= */
192
193int kth_smallest(int arr[], int n, int k) {
194    MaxHeap* heap = maxheap_create(k);
195
196    for (int i = 0; i < n; i++) {
197        if (heap->size < k) {
198            maxheap_push(heap, arr[i]);
199        } else if (arr[i] < heap->data[0]) {
200            maxheap_pop(heap);
201            maxheap_push(heap, arr[i]);
202        }
203    }
204
205    int result = heap->data[0];
206    maxheap_free(heap);
207    return result;
208}
209
210int kth_largest(int arr[], int n, int k) {
211    MinHeap* heap = minheap_create(k);
212
213    for (int i = 0; i < n; i++) {
214        if (heap->size < k) {
215            minheap_push(heap, arr[i]);
216        } else if (arr[i] > heap->data[0]) {
217            minheap_pop(heap);
218            minheap_push(heap, arr[i]);
219        }
220    }
221
222    int result = heap->data[0];
223    minheap_free(heap);
224    return result;
225}
226
227/* =============================================================================
228 * 5. ์ค‘์•™๊ฐ’ ์ฐพ๊ธฐ (๋‘ ๊ฐœ์˜ ํž™)
229 * ============================================================================= */
230
231typedef struct {
232    MaxHeap* lower;  /* ํ•˜์œ„ ์ ˆ๋ฐ˜ (์ตœ๋Œ€ ํž™) */
233    MinHeap* upper;  /* ์ƒ์œ„ ์ ˆ๋ฐ˜ (์ตœ์†Œ ํž™) */
234} MedianFinder;
235
236MedianFinder* median_finder_create(int capacity) {
237    MedianFinder* mf = malloc(sizeof(MedianFinder));
238    mf->lower = maxheap_create(capacity);
239    mf->upper = minheap_create(capacity);
240    return mf;
241}
242
243void median_finder_free(MedianFinder* mf) {
244    maxheap_free(mf->lower);
245    minheap_free(mf->upper);
246    free(mf);
247}
248
249void median_finder_add(MedianFinder* mf, int num) {
250    /* lower์— ์ถ”๊ฐ€ */
251    maxheap_push(mf->lower, num);
252
253    /* lower์˜ ์ตœ๋Œ“๊ฐ’์„ upper๋กœ */
254    minheap_push(mf->upper, maxheap_pop(mf->lower));
255
256    /* ๊ท ํ˜• ๋งž์ถ”๊ธฐ */
257    if (mf->upper->size > mf->lower->size) {
258        maxheap_push(mf->lower, minheap_pop(mf->upper));
259    }
260}
261
262double median_finder_get(MedianFinder* mf) {
263    if (mf->lower->size > mf->upper->size)
264        return mf->lower->data[0];
265    return (mf->lower->data[0] + mf->upper->data[0]) / 2.0;
266}
267
268/* =============================================================================
269 * 6. K๊ฐœ ์ •๋ ฌ ๋ฆฌ์ŠคํŠธ ๋ณ‘ํ•ฉ
270 * ============================================================================= */
271
272typedef struct {
273    int val;
274    int list_idx;
275    int elem_idx;
276} HeapNode;
277
278typedef struct {
279    HeapNode* data;
280    int size;
281    int capacity;
282} NodeHeap;
283
284NodeHeap* nodeheap_create(int capacity) {
285    NodeHeap* heap = malloc(sizeof(NodeHeap));
286    heap->data = malloc(capacity * sizeof(HeapNode));
287    heap->size = 0;
288    heap->capacity = capacity;
289    return heap;
290}
291
292void nodeheap_push(NodeHeap* heap, HeapNode node) {
293    int idx = heap->size++;
294    heap->data[idx] = node;
295
296    while (idx > 0) {
297        int parent = (idx - 1) / 2;
298        if (heap->data[parent].val <= heap->data[idx].val)
299            break;
300        HeapNode temp = heap->data[parent];
301        heap->data[parent] = heap->data[idx];
302        heap->data[idx] = temp;
303        idx = parent;
304    }
305}
306
307HeapNode nodeheap_pop(NodeHeap* heap) {
308    HeapNode min = heap->data[0];
309    heap->data[0] = heap->data[--heap->size];
310
311    int idx = 0;
312    while (2 * idx + 1 < heap->size) {
313        int smallest = idx;
314        int left = 2 * idx + 1;
315        int right = 2 * idx + 2;
316
317        if (heap->data[left].val < heap->data[smallest].val)
318            smallest = left;
319        if (right < heap->size && heap->data[right].val < heap->data[smallest].val)
320            smallest = right;
321
322        if (smallest == idx) break;
323
324        HeapNode temp = heap->data[idx];
325        heap->data[idx] = heap->data[smallest];
326        heap->data[smallest] = temp;
327        idx = smallest;
328    }
329
330    return min;
331}
332
333int* merge_k_sorted(int** lists, int* sizes, int k, int* result_size) {
334    *result_size = 0;
335    for (int i = 0; i < k; i++)
336        *result_size += sizes[i];
337
338    int* result = malloc(*result_size * sizeof(int));
339    NodeHeap* heap = nodeheap_create(k);
340
341    /* ๊ฐ ๋ฆฌ์ŠคํŠธ์˜ ์ฒซ ์›์†Œ๋ฅผ ํž™์— ์ถ”๊ฐ€ */
342    for (int i = 0; i < k; i++) {
343        if (sizes[i] > 0) {
344            nodeheap_push(heap, (HeapNode){lists[i][0], i, 0});
345        }
346    }
347
348    int idx = 0;
349    while (heap->size > 0) {
350        HeapNode min_node = nodeheap_pop(heap);
351        result[idx++] = min_node.val;
352
353        /* ๊ฐ™์€ ๋ฆฌ์ŠคํŠธ์˜ ๋‹ค์Œ ์›์†Œ ์ถ”๊ฐ€ */
354        if (min_node.elem_idx + 1 < sizes[min_node.list_idx]) {
355            int next_val = lists[min_node.list_idx][min_node.elem_idx + 1];
356            nodeheap_push(heap, (HeapNode){next_val, min_node.list_idx, min_node.elem_idx + 1});
357        }
358    }
359
360    free(heap->data);
361    free(heap);
362    return result;
363}
364
365/* =============================================================================
366 * ํ…Œ์ŠคํŠธ
367 * ============================================================================= */
368
369void print_array(int arr[], int n) {
370    printf("[");
371    for (int i = 0; i < n; i++) {
372        printf("%d", arr[i]);
373        if (i < n - 1) printf(", ");
374    }
375    printf("]");
376}
377
378int main(void) {
379    printf("============================================================\n");
380    printf("ํž™ (Heap) ์˜ˆ์ œ\n");
381    printf("============================================================\n");
382
383    /* 1. ์ตœ์†Œ ํž™ */
384    printf("\n[1] ์ตœ์†Œ ํž™\n");
385    MinHeap* min_heap = minheap_create(10);
386    int vals[] = {5, 3, 8, 1, 2, 9, 4};
387    printf("    ์‚ฝ์ž…: ");
388    print_array(vals, 7);
389    printf("\n");
390
391    for (int i = 0; i < 7; i++)
392        minheap_push(min_heap, vals[i]);
393
394    printf("    ์ถ”์ถœ: ");
395    while (min_heap->size > 0)
396        printf("%d ", minheap_pop(min_heap));
397    printf("\n");
398    minheap_free(min_heap);
399
400    /* 2. ์ตœ๋Œ€ ํž™ */
401    printf("\n[2] ์ตœ๋Œ€ ํž™\n");
402    MaxHeap* max_heap = maxheap_create(10);
403    for (int i = 0; i < 7; i++)
404        maxheap_push(max_heap, vals[i]);
405
406    printf("    ์ถ”์ถœ: ");
407    while (max_heap->size > 0)
408        printf("%d ", maxheap_pop(max_heap));
409    printf("\n");
410    maxheap_free(max_heap);
411
412    /* 3. ํž™ ์ •๋ ฌ */
413    printf("\n[3] ํž™ ์ •๋ ฌ\n");
414    int arr3[] = {12, 11, 13, 5, 6, 7};
415    printf("    ์ •๋ ฌ ์ „: ");
416    print_array(arr3, 6);
417    printf("\n");
418    heap_sort(arr3, 6);
419    printf("    ์ •๋ ฌ ํ›„: ");
420    print_array(arr3, 6);
421    printf("\n");
422
423    /* 4. K๋ฒˆ์งธ ์›์†Œ */
424    printf("\n[4] K๋ฒˆ์งธ ์›์†Œ\n");
425    int arr4[] = {7, 10, 4, 3, 20, 15};
426    printf("    ๋ฐฐ์—ด: ");
427    print_array(arr4, 6);
428    printf("\n");
429    printf("    3๋ฒˆ์งธ ์ตœ์†Œ: %d\n", kth_smallest(arr4, 6, 3));
430    printf("    2๋ฒˆ์งธ ์ตœ๋Œ€: %d\n", kth_largest(arr4, 6, 2));
431
432    /* 5. ์ค‘์•™๊ฐ’ ์ฐพ๊ธฐ */
433    printf("\n[5] ์ŠคํŠธ๋ฆผ ์ค‘์•™๊ฐ’\n");
434    MedianFinder* mf = median_finder_create(10);
435    int stream[] = {2, 3, 4};
436    for (int i = 0; i < 3; i++) {
437        median_finder_add(mf, stream[i]);
438        printf("    ์‚ฝ์ž… %d ํ›„ ์ค‘์•™๊ฐ’: %.1f\n", stream[i], median_finder_get(mf));
439    }
440    median_finder_free(mf);
441
442    /* 6. K๊ฐœ ์ •๋ ฌ ๋ฆฌ์ŠคํŠธ ๋ณ‘ํ•ฉ */
443    printf("\n[6] K๊ฐœ ์ •๋ ฌ ๋ฆฌ์ŠคํŠธ ๋ณ‘ํ•ฉ\n");
444    int list1[] = {1, 4, 5};
445    int list2[] = {1, 3, 4};
446    int list3[] = {2, 6};
447    int* lists[] = {list1, list2, list3};
448    int sizes[] = {3, 3, 2};
449
450    int result_size;
451    int* merged = merge_k_sorted(lists, sizes, 3, &result_size);
452    printf("    ๋ณ‘ํ•ฉ ๊ฒฐ๊ณผ: ");
453    print_array(merged, result_size);
454    printf("\n");
455    free(merged);
456
457    /* 7. ํž™ ์—ฐ์‚ฐ ๋ณต์žก๋„ */
458    printf("\n[7] ํž™ ์—ฐ์‚ฐ ๋ณต์žก๋„\n");
459    printf("    | ์—ฐ์‚ฐ      | ์‹œ๊ฐ„๋ณต์žก๋„ |\n");
460    printf("    |-----------|------------|\n");
461    printf("    | ์‚ฝ์ž…      | O(log n)   |\n");
462    printf("    | ์‚ญ์ œ(์ตœ์†Œ)| O(log n)   |\n");
463    printf("    | ์กฐํšŒ(์ตœ์†Œ)| O(1)       |\n");
464    printf("    | ํž™ ๊ตฌ์„ฑ   | O(n)       |\n");
465    printf("    | ํž™ ์ •๋ ฌ   | O(n log n) |\n");
466
467    printf("\n============================================================\n");
468
469    return 0;
470}