힙 (Heap)

삽입 시간 복잡도 -> O(logn)

삭제 시간 복잡도 -> O(logn)

 

/*
    코드 출처 : C언어로 쉽게 풀어쓴 자료구조 / 생능출판 / 천인국, 공용해, 하상호 지음
*/
#include <stdio.h>
#define MAX_ELEMENT 200

typedef struct {
    int key;
} element;

typedef struct {
    element heap[MAX_ELEMENT];
    int heap_size;
} HeapType;

//초기화 함수
init(HeapType *h) { h->heap_size = 0; }

//삽입 함수
void insert_max_heap(HeayType *h, element item)
{
    int i;
    i = ++(h->heap_size);
    
    while((i != 1) && (item.key > h->heap[i/2].key)) {
        h->heap[i] = h->heap[i/2];
        i /= 2;
    }
    h->heap[i] = item;
}

//삭제 함수
element delete_max_heap(HeapType *h)
{
    int parent, child;
    element item, temp;
    
    item = h->heap[1];
    temp = h->heap[(h->heap_size)--];
    parent = 1;
    child = 2;
    
    while(child <= h->heap_size) {
	    if((child < h->heap_size) && (h->heap[child].key) < h->heap[child+1].key) {
        	child++;
        }
        if(temp.key >= h->heap[child].key) break;
        
        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
	}
    
    h->heap[parent] = temp;
    return item;
}

void main() {
    element e1 = {10}, e2 = {5}, e3 = {30};
    element e4, e5, e6;
    HeapType heap;
    init(&heap);
    
    insert_max_heap(&heap, e1);
    insert_max_heap(&heap, e2);
    insert_max_heap(&heap, e3);
    
    e4 = delete_max_heap(&heap);
    e5 = delete_max_heap(&heap);
    e6 = delete_max_heap(&heap);
    
    printf("%d %d %d\n", e4.key, e5.key, e6.key);
}