히프의 구현

- 히프는 1차원 배열로 표현될 수 있음

- 히프의 각 요소들을 구조체 element로 정의하고, element의 1차원 배열을 만들어 히프 구현

#define MAX_ELEMENT 200

typedef struct {
	int key;
} element;
typedef struct {
	element heap[MAX_ELEMENT];
	int heap_size;	//현재 히프 안에 저장된 요소 개수
} HeapType;

 

- 히프를 생성하려면 아래와 같은 방법을 사용

HeapType heap;
HeapType* heap = create();	//동적 할당 이용

---

삽입 연산

- 히프에 새로운 요소가 들어오면, 일단 새로운 노드를 히프의 마지막 노드로 삽입

- 삽입 후에 새로운 노드를 부모 노드들과 교환하여 히프의 성질을 만족하도록 함

- 히프 크기를 1 증가

- 증가된 히프 크기 위치에 새로운 노드 삽입

- i가 루트 노드가 아니고 i번째 노드가 i의 부모 노드보다 크면

- i번째 노드와 부모 노드를 교환

//최대 히프에서
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;	//새로운 노드 삽입
}

---

삭제 연산

- 최대 히프에서 삭제 연산은 루트 노드를 삭제하는 것

- 루트 노드 삭제 후 히프 재구성 필요(히프의 성질을 만족하기 위해 위, 아래 노드 교환)

- 루트 노드 반환을 위해 루트 노드를 item 변수에 저장

- 말단 노드를 루트 노드로 이동

- 히프 크기 1 감소

- 루트의 왼쪽 자식부터 비교

- i가 히프 트리 크기보다 작을 때(=히프 트리를 벗어나지 않으면) 아래 과정을 반복

- 오른쪽 자식이 더 크면 두 자식 노드 중 큰 값의 인덱스를 largest로 이동

- largest의 부모 노드가 largest보다 크면 중지

- 그렇지 않으면 largest와 largest의 부모 노드를 교환

- 한 레벨 아래로

- 최대값 반환

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;
}

---

히프 복잡도 분석

 

1. 삽입 연산

- 히프 트리를 타고 올라가며 부모 노드들과 교환

- 최악의 경우 루트 노드까지 올라가야 하므로 트리의 높이에 해당하는 비교 연산 또는 이동 연산이 필요

- 히프는 완전 이진 트리이므로 히프의 높이는 log₂n, 시간 복잡도는 O log₂n)

 

2. 삭제 연산

- 마지막 노드를 루트로 가져온 뒤 자식 노드들과 비교하여 교환

- 최악의 경우 최하위 레벨까지 내려가야 하므로 트리 높이만큼이 시간 소요

- 삭제의 시간 복잡도 또한 O(log₂n)

---

전체 프로그램

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200

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

//생성
HeapType* create() {
	return (HeapType*)malloc(sizeof(HeapType));
}
//초기화
void init(HeapType* h) {
	h->heap_size = 0;
}
//삽입
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;
}

int main(void) {
	element e1 = { 10 }, e2 = { 5 }, e3 = { 30 };
	element e4, e5, e6;
	HeapType* heap;

	heap = create();
	init(heap);

	//삽입
	insert_max_heap(heap, e1);
	insert_max_heap(heap, e2);
	insert_max_heap(heap, e3);

	//삭제
	e4 = delete_max_heap(heap);
	printf("< %d > ", e4.key);
	e5 = delete_max_heap(heap);
	printf("< %d > ", e5.key);
	e6 = delete_max_heap(heap);
	printf("< %d > ", e6.key);

	free(heap);
	return 0;
}

>>