[자료구조] 우선순위 큐와 힙2

힙의 구현에 어울리는 것은? 연결리스트 아니라 배열

앞서 우선순위 큐의 구현에 어울리는 것은 힙으로 결론이 났다.

그렇다면 힙의 구현방법에 대해서 고민해보자. 힙은 트리이고 트리를 구현하는 방법에는 배열과 연결리스트가 있다. 이 둘 중 뭘 이용해야 할까?

 

정답은 배열이다.

완전 이진 트리의 구조를 갖고 또 그 구조를 유지해야 하는 힙은 배열 기반으로 구현해야 한다.

 

연결리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 '마지막 위치'에 추가하는 것이 쉽지 않기 때문이다.

 

배열 기반 힙을 구현하려면?

배열을 기반으로 투리를 구성하는 방법을 요약하자면 다음과 같다.

노드에 고유의 번호를 부여한다. 그리고 그 번호가 각 노드의 데이터가 저장 될 배열이 인덱스 값이 된다.

 

위 문장을 그림으로 설명하자면 다음과 같다.

 

구현의 편의를 위해 인덱스가 0인 위치의 배열요소는 사용하지 않는다.

 

그렇다면, 배열 기반으로 힙을 구현하기 위해선, 

1.왼쪽과 오른쪽 자식 노드의 인덱스 값을 얻는 방법, 2. 부모 노드의 인덱스 값을 얻는 방법을 알아야 한다.

 

1은 데이터의 삭제를 위해서, 2는 데이터의 추가를 위해서 필요하다.

 

그럼 이 두 가지 방법을 소개하겠다.

왼쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 * 2
오른쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 * 2 + 1
부모 노드의 인덱스 값 : 자식 노드의 인덱스 값 / 2 (정수형 나눗셈 : 나머지는 버린다)

 

 

원리 이해 중심의 힙 구현

힙을 구현하기 전 다음과 같은 사실들을 짚고 넘어가자

• 힙은 완전 이진 트리이다.
• 힙의 구현은 배열을 기반으로 하며 인덱스가 0인 요소는 비워둔다.
• 따라서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다.
• 노드의 고유번호가 노드가 저장되는 배열의 인덱스 값이 된다.
• 우선순위를 나타내는 정수 값이 작을수록 높은 우선순위를 나타낸다고 가정한다. (이건 프로그래머가 설정 가능)

1. 헤더파일

#ifndef __SIMPLE_HEAP_H__
#define __SIMPLE_HEAP_H__

#define TRUE	1
#define FALSE	0

#define HEAP_LEN	100

typedef char HData;
typedef int Priority;

typedef struct _heapElem
{
	Priority pr;	// 값이 작을수록 높은 우선순위
	HData data;
} HeapElem;

typedef struct _heap
{
	int numOfData;
	HeapElem heapArr[HEAP_LEN];
} Heap;

/*** Heap 관련 연산들 ****/
void HeapInit(Heap * ph);
int HIsEmpty(Heap * ph);

void HInsert(Heap * ph, HData data, Priority pr);
HData HDelete(Heap * ph);

#endif

 

2. 힙의 구현  - 높은 우선순위 반환

#include "SimpleHeap.h"

void HeapInit(Heap * ph) // 힙의 초기화
{
	ph->numOfData = 0;
}

int HIsEmpty(Heap * ph) // 힙이 비었는지 확인
{
	if(ph->numOfData == 0)
		return TRUE;
	else
		return FALSE;
}

int GetParentIDX(int idx) // 자신의 부모 노드의 인덱스 값 반환
{ 
	return idx/2; 
}

int GetLChildIDX(int idx) // 자신의 왼쪽 자식 노드의 인덱스 값 반환
{ 
	return idx*2; 
}

int GetRChildIDX(int idx) // 자신의 오른쪽 자식 노드의 인덱스 값 반환
{ 
	return GetLChildIDX(idx)+1; 
}

// 두 개의 자식 노드 중 높은 우선순위의 자식 노드 인덱스 값 반환
int GetHiPriChildIDX(Heap * ph, int idx)
{
	if(GetLChildIDX(idx) > ph->numOfData)    // 자식 노드가 없다면
		return 0;

	else if(GetLChildIDX(idx) == ph->numOfData)    // 왼쪽 자식 노드가 마지막 노드라면
		return GetLChildIDX(idx);

	else   // 왼쪽 자식 노드와 오른쪽 자식 노드의 우선순위를 비교
	{
		if(ph->heapArr[GetLChildIDX(idx)].pr 
						> ph->heapArr[GetRChildIDX(idx)].pr)
			return GetRChildIDX(idx);
		else
			return GetLChildIDX(idx);
	}
}

 

3. 힙의 구현  - 힙에 데이터 삽입과 삭제

//힙에 데이터 저장
void HInsert(Heap * ph, HData data, Priority pr)
{
	int idx = ph->numOfData+1;
	HeapElem nelem = {pr, data}; 

	while(idx != 1)
	{
		if(pr < (ph->heapArr[GetParentIDX(idx)].pr))
		{
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
		}
		else
			break;
	}
	
	ph->heapArr[idx] = nelem;
	ph->numOfData += 1;
}


//힙에 데이터 삭제
HData HDelete(Heap * ph)
{
	HData retData = (ph->heapArr[1]).data;    // 힙의 루트 노드에 저장된 데이터(삭제할 데이터) 임시 변수 retData에 저장
	HeapElem lastElem = ph->heapArr[ph->numOfData]; // 힙의 마지막 노드에 저장된 데이터 lastElem 변수에 저장
 
    // 아래 parentIdx에는 마지막 노드가 저장될 위치정보가 담긴다.
	int parentIdx = 1; // 루트 노드가 위치해야 할 인덱스 값 저장   
	int childIdx; 
    
    // 루트 노드의 우선 순위가 높은 자식 노드를 시작으로 반복문 시작
	while(childIdx = GetHiPriChildIDX(ph, parentIdx))
	{
		if(lastElem.pr <= ph->heapArr[childIdx].pr) // 마지막 노드와 우선순위 비교
			break; // 마지막 노드의 우선순위가 높으면 반복문 탈출

	// 마지막 노드보다 우선순위 높으니, 비교대상 노드의 위치를 한 레벨 올림
		ph->heapArr[parentIdx] = ph->heapArr[childIdx]; 
		parentIdx = childIdx;
	} //반복문 탈출시, parentIdx에는 마지막 노드의 위치정보가 저장됨

	ph->heapArr[parentIdx] = lastElem; //마지막 노드 최종 저장
	ph->numOfData -= 1;
	return retData;
}

 

 

(윤성우의 열혈 자료구조를 참고하여 작성하였습니다.)