Chapter 12. 힙(Heap)

Def) 힙(Heap)

  완전 이진 트리의 한 분류로서, 힙 속성을 만족하는 자료구조. 이진 힙(Binary Heap)

 

Note) 힙 속성(Heap Property)

  - 최대 힙 속성(Max Heap Property)

    부모 노드의 키 값은 항상 자식 노드의 키 값보다 크거나 같다.

  - 최소 힙 속성(Min Heap Property)

    부모 노드의 키 값은 항상 자식 노드의 키 값보다 작거나 같다.

 

Note) 힙의 특징

  - 루트 노드는 항상 최댓값 또는 최솟값을 갖음.

  - 부모 - 자식 사이의 크기 관계만 있고,

    왼쪽 자식 - 오른쪽 자식 사이의 크기 관계는 없음.

  - 완전 이진 트리이기 때문에 트리의 높이 h = [log2N]

  - 힙의 응용 분야

    힙 정렬, 우선순위 큐, 다익스트라 알고리즘 등

 

	힙	이진 탐색 트리
트리의 분류	완전 이진 트리	이진 트리
원소 중복 여부	중복 가능	중복 불가능
원소의 정렬 여부	정렬 안됨	정렬 됨(중위 탐색시)
빠른 원소 탐색	미지원(순차 탐색, O(N))	지원(이진 탐색, O(logN))
원소의 삽입 또는 삭제	O(logN)	O(logN) or O(N)
최댓값 / 최솟값 참조	O(1)	O(logN) or O(N)

 

Note) 힙의 구현

  - 완전 이진 트리이므로 각 노드에 인덱스를 붙히는 식으로

    배열을 활용하여 구현 가능함.

  - 구현의 편의상 루트 노드의 인덱스를 1로 지정. 0번 인덱스는 무시.

  - 인덱스가 n인 노드에 대해서

    부모 노드의 인덱스는 n / 2

    왼쪽 자식 노드의 인덱스는 n * 2

    오른쪽 자식 노드의 인덱스는 n * 2 + 1

 

Thm) 힙의 삽입

  - 힙의 맨 마지막에 새로운 원소 값을 갖는 노드를 추가

  - 새로 삽입한 노드와 부모 노드를 서로 비교

    힙 속성을 만족하지 않으면 삽입 노드와 부모 노드 교환

  - 다시 부모 노드와 이 작업을 반복.

 

Thm) 힙의 삭제

  - 힙의 맨 마지막 노드 값을 루트 노드로 복사 후

    맨 마지막 노드를 삭제

  - 루트 노드부터 두 자식 노드를 비교 후 

    힙 속성을 만족하지 않으면 두 자식 노드 중

    더 큰 노드와 서로 교환

  - 다시 자식 노드들과 이 작업을 반복.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>

// 함수 호출에 의한 오버헤드를 줄이기 위함.
#define PARENT(INDEX) (INDEX / 2)
#define LEFT(INDEX) (INDEX * 2)
#define RIGHT(INDEX) (INDEX * 2 + 1)

enum {
	FALSE = 0,
	TRUE = 1,
	INVALIED_INDEX = -1,
	MAX_COUNT = 1001
};

typedef struct heap {
	int nArray[MAX_COUNT];
	size_t uCount;
} heap_t;

void push(heap_t* _pHeap, int  _nData);
void heapify_up(heap_t* _pHeap, size_t _uIdx);
int isEmpty(heap_t* _pHeap);
int pop(heap_t* _pHeap);
void heapify_down(heap_t* _pHeap, size_t _uIdx);
int top(heap_t* _pHeap);
int size(heap_t* _pHeap);

int main(void)
{
	heap_t heap = {0,};
	heap.uCount = 1;
	push(&heap, 10); push(&heap, 5);
	push(&heap, 15); push(&heap, 7);
	push(&heap, 3); push(&heap, 9);
	push(&heap, 14); push(&heap, 8);
	push(&heap, 2); push(&heap, 4);

	while (FALSE == isEmpty(&heap))
	{
		printf("%d, ", pop(&heap));
	}

	return 0;
}

void push(heap_t* _pHeap, int  _nData)
{
	assert(_pHeap->uCount < MAX_COUNT);

	_pHeap->nArray[_pHeap->uCount++] = _nData;
	heapify_up(_pHeap, _pHeap->uCount - 1);
}
void heapify_up(heap_t* _pHeap, size_t _uIdx)
{
	if (1 < _uIdx && _pHeap->nArray[PARENT(_uIdx)] < _pHeap->nArray[_uIdx])
	{
		int nTemp = _pHeap->nArray[PARENT(_uIdx)];
		_pHeap->nArray[PARENT(_uIdx)] = _pHeap->nArray[_uIdx];
		_pHeap->nArray[_uIdx] = nTemp;
		heapify_up(_pHeap, PARENT(_uIdx));
	}
}

int isEmpty(heap_t* _pHeap)
{
	if (2 <= _pHeap->uCount)
	{
		return FALSE;
	}
	return TRUE;
}

int pop(heap_t* _pHeap)
{
	int ret = _pHeap->nArray[1];
	_pHeap->nArray[1] = _pHeap->nArray[--_pHeap->uCount];
	heapify_down(_pHeap, 1);
	return ret;
}

void heapify_down(heap_t* _pHeap, size_t _uIdx)
{
	size_t uLargest = _uIdx;

	if (LEFT(_uIdx) < _pHeap->uCount && _pHeap->nArray[uLargest] < _pHeap->nArray[LEFT(_uIdx)])
	{
		uLargest = LEFT(_uIdx);
	}

	if (RIGHT(_uIdx) < _pHeap->uCount && _pHeap->nArray[uLargest] < _pHeap->nArray[RIGHT(_uIdx)])
	{
		uLargest = RIGHT(_uIdx);
	}

	if (uLargest != _uIdx)
	{
		int nTemp = _pHeap->nArray[_uIdx];
		_pHeap->nArray[_uIdx] = _pHeap->nArray[uLargest];
		_pHeap->nArray[uLargest] = nTemp;
		heapify_down(_pHeap, uLargest);
	}
}

int top(heap_t* _pHeap)
{
	return _pHeap->nArray[1];
}

int size(heap_t* _pHeap)
{
	return _pHeap->uCount - 1;
}