[자료구조] 히프 (Heap)

1) 히프(Heap)

• 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조
• 최대 히프(Max Heap)
  • 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
  • {부모 노드의 키 값 ≥ 자식 노드의 키 값}
  • 루트 노드 : 키 값이 가장 큰 노드
• 최소 히프(Min Heap)
  • 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
  • {부모 노드의 키 값 ≤ 자식 노드의 키 값}
  • 루트 노드: 키 값이 가장 작은 노드

2) 히프의 삽입 연산

• 1단계 : 완전 이진 트리를 유지하면서 확장한 노드에 삽입할 원소를 임시 저장
  • 노드가 n개인 완전 이진 트리에서 다음 노드의 확장 자리는 n+1번의 노드가 됨
  • n+1번 자리에 노드를 확장하고, 그 자리에 삽입할 원소를 임시 저장함

• 2단계 : 만들어진 완전 이진 트리 내에서 삽입 원소의 제자리를 찾음
  • 현재 위치에서 부모 노드와 비교하여 크기 관계를 확인함
  • 최대 히프의 경우 {현재 부모 노드의 키 값 ≥ 삽입 원소의 키 값}의 관계가 성립하지 않으면, 현재 부모 노드의 원소와 삽입 원소의 자리를 서로 바꿈

3) 히프의 삭제 연산

• 히프에서는 루트 노드의 원소 만을 삭제 할 수 있음
• 1단계 : 루트 노드의 원소를 삭제하여 반환함
• 2단계 : 원소의 개수가 n-1개로 줄었으므로, 노드의 수가 n-1인 완전 이진 트리로 조정함
  • 노드가 n개인 완전 이진 트리에서 노드 수 n-1개의 완전 이진 트리가 되기 위해서 마지막 노드, 즉 n번 노드를 삭제함
  • 삭제된 n번 노드에 있던 원소는 비어있는 루트 노드에 임시 저장함

• 3단계 : 완전 이진 트리 내에서 루트에 임시 저장된 원소의 제자리를 찾음
  • 현재 위치에서 자식 노드와 비교하여 크기 관계를 확인함
  • {임시 저장 원소의 키 값 ≥ 현재 자식 노드의 키 값}의 관계가 성립하지 않으면, 현재 자식 노드의 원소와 임시 저장 원소의 자리를 서로 바꿈

4) 히프 구현

소스코드

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

typedef int element;

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

heapType* createHeap()
{
	heapType* h = (heapType*)malloc(sizeof(heapType));
	h->heap_size = 0;
	return h;
}

void insertHeap(heapType* h, element item)
{
	int i;
	h->heap_size++;
	i = h->heap_size;
	while ((i != 1) && (item > h->heap[i / 2]))
	{
		h->heap[i] = h->heap[i / 2];
		i /= 2;
	}
	h->heap[i] = item;
}

int deleteHeap(heapType* h)
{
	int parent, child;
	element item, temp;
	item = h->heap[1];
	temp = h->heap[h->heap_size];
	h->heap_size--;
	parent = 1;
	child = 2;
	while (child <= h->heap_size)
	{
		if ((child < h->heap_size) && (h->heap[child] < h->heap[child + 1]))
			child++;
		if (temp >= h->heap[child]) break;
		else
		{
			h->heap[parent] = h->heap[child];
			parent = child;
			child *= 2;
		}
	}
	h->heap[parent] = temp;
	return item;
}

void printHeap(heapType* h)
{
	int i;
	printf("Heap : ");
	for (i = 1; i <= h->heap_size; i++)
		printf("[%d] ", h->heap[i]);
}

void main()
{
	int i, n;
	element item;
	heapType* heap = createHeap();
	insertHeap(heap, 10);
	insertHeap(heap, 45);
	insertHeap(heap, 19);
	insertHeap(heap, 11);
	insertHeap(heap, 96);
	
	printHeap(heap);

	n = heap->heap_size;
	for (i = 1; i <= n; i++)
	{
		item = deleteHeap(heap);
		printf("\n delete : [%d] ", item);
	}

	getchar();
}

실행 결과