히프
- 우선순위 큐를 위해 만들어진 자료구조
- 노드들이 저장하고 있는 키들이 다음과 같은 식을 만족하는 완전이진트리
n 개의 노드를 가지고 있는 히프의 높이 logn
배열을 이용한 구현
부모 노드와 자식 노드 찾기 쉬움
#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);
}
}