히프 (heap)

히프
- 우선순위 큐를 위해 만들어진 자료구조
- 노드들이 저장하고 있는 키들이 다음과 같은 식을 만족하는 완전이진트리

최대 히프 (max heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• key(부모노드) >= key(자식노드)

최소 히프 (min heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• key(부모노드) <= key(자식노드)

히프의 높이

n 개의 노드를 가지고 있는 히프의 높이 logn

• 히프는 완전이진트리
• 마지막 레벨 h을 제외하고는 각 레벨 i에 2^(i-1) 개의 노드 존재

구현 방법

배열을 이용한 구현

• 완전이진트리이므로 각 노드에 번호를 붙일 수 있음
• 이 번호를 배열의 인덱스라고 생각

부모 노드와 자식 노드 찾기 쉬움

• 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
• 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
• 부모의 인덱스 = (자식의 인덱스) / 2

구조체 구현

#define MAX_ELEMENT 200
typedef struct{
	int key;
} element;

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

삽입

void insert_max_heap(HeapType *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 heap_sort(element a[], int n){
	int i;
    HeapType *h;
    
    h = create();
    init(h);
    for(i = 0; i < n; i++){
    	insert_max_heap(h, a[i]);
    }
    for(i=(n-1); i >= 0; i--){
    	a[i] = delete_max_heap(h);
    }
}