우선순위 큐(Priority Queue)와 힙(Heap)

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.

 

1. 우선순위 큐의 이해

1.1. 우선순위 큐와 우선순위의 이해

• 우선순위 큐도 enqueue와 dequeue가 일반 큐와 같음
• 하지만 우선순위 큐의 결과는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옴

1.2. 우선순위 큐의 구현 방법

• 배열 기반으로 구하는 방법
• 연결 리스트를 기반으로 구현하는 방법
• 힙(heap)을 이용하는 방법

• 배열의 경우, 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시킴
• 데이터 반환 및 소멸은 쉽지만 데이터를 삽입 및 삭제하는 과정에서 데이터를 계속 한 칸씩 뒤로 밀거나 당기는 연산을 수반해야 하는 문제가 생김
• 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위 비교를 진행해야 할 수 있음
• 연결 리스트의 경우, 삽입의 위치를 찾기 위해서 첫 번째 노드에서부터 시작하여 마지막 노드에 저장된 데이터와 비교해야 할 수도 있는 문제가 있음

1.3. 힙(heap)의 소개

• 힙은 완전 이진 트리로 이루어져 있음
• 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 함.
• 즉, 루트 노드가 가장 커야 함

 

2. 힙의 구현과 우선순위 큐의 완성

2.1. 힙에서의 데이터 저장과정

• 새로운 데이터는 우선순위가 제일 낮다는 가정 하에 마지막 위치에 저장
• 이후 부모 노드와 우선순위를 비교하여 위치를 바꿔야 할 경우 교체
• 제대로 된 위치를 찾을 때까지 계속 진행

2.2. 힙에서의 데이터 삭제과정

• 우선순위 큐에서의 삭제는 가장 높은 우선순위의 데이터 삭제를 의미
• 마지막 노드를 루트 노드 자리로 옮긴 후 자식 노드와의 비교를 통해 자기 자리를 찾게 함.
• 이때 루트 노드와 왼쪽 자식과 오른쪽 자식 중 우선순위가 더 높은 노드를 먼저 비교해야 함.

2.3. 삽입/삭제 성능 평가 및 힙 구현 자료구조

• 배열
  • 데이터 저장 시간 복잡도: O(n)
  • 데이터 삭제 시간 복잡도: O(1)
• 연결리스트
  • 데이터 저장 시간 복잡도: O(n)
  • 데이터 삭제 시간 복잡도: O(1)
• 힙
  • 데이터 저장 시간 복잡도: O(logn)
  • 데이터 삭제 시간 복잡도: O(logn)
• 의외로 힙은 배열을 기반으로 구현해야 함.
• 연결리스트 기반으로 힙을 구현할 경우, 새로운 노드를 힙의 마지막 위치에 추가하는 것이 어려움
• 부모 노드의 인덱스 값: n
• 왼쪽 자식 노드의 인덱스 값: 2*n
• 오른쪽 자식 노드의 인덱스 값: 2*n + 1

2.4. 힙의 구현

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

typedef char HData;
typedef int Priority;

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

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

void HeapInit(Heap * ph);
int HIsEmpty(Heap * ph);

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

 

• 구현 코드

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 idx*2 + 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);   // 왼쪽 자식 노드의 인덱스 값 반환
	}
}

// 힙에 데이터 저장
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] = heapArr[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
	}
	
	ph->heapArr[idx] = nelem;
	ph->numOfData += 1; 
}

// 힙에서 데이터 삭제
HData HDelete(Heap *ph)
{
	HData retData = (ph->heapArr[1]).data;  // 반환을 위해서 삭제할 데이터 저장
	HeapElem lastElem = ph->heapArr[ph->numOfData];  // 힙의 마지막 노드 저장
	
	// 아래의 변수 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;  // 마지막 노드가 저장될 위치 정보를 한 레벨 내림
	}
	
	ph->heapArr[parentIdx] = lastElem;  // 마지막 노드 최종 저장
	ph->numOfData -= 1;
	return retData;
}

• 변경점
  • 우선순위를 매번 정해서 알려줘야 함.
  • 우선순위의 판단 기준을 힙에 설정할 수 있어야 함
• 수정
  • heapElem의 역할이 없어져 삭제됨
  • heap 구조에 두 개의 데이터를 대상으로 우선순위가 낮고 높음을 판단하는 함수를 등록하기 위한 포인터 변수 comp 등록

 

• 변경점만 정리한 코드

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

typedef char HData;
typedef int (*PriorityComp)(HData d1, HData d2);

typedef struct _heap
{
	PriorityComp *comp; // 추가
	int numOfData;
	HeapElem heapArr[HEAP_LEN];
} Heap;

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

... 나머지 동일

// 두 개의 자식 노드 중 높은 우선순위의 자식 노드 인덱스 값 반환
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)
		if(ph->comp(ph->heapArr[GetLChildIDX(idx)], ph->heapArr[GetRChildIDX(idx)]) < 0) // 대체
			return GetRChildIDX(idx);   // 오른쪽 자식 노드 인덱스 값 반환
		else
			return GetLChildIDX(idx);   // 왼쪽 자식 노드의 인덱스 값 반환
	}
}

// 힙에 데이터 저장
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);
		if(ph->comp(data, ph->heapArr[GetParentIDX(idx)]) > 0) // 대체
			ph->heapArr[idx] = heapArr[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
	}
	
	ph->heapArr[idx] = nelem;
	ph->numOfData += 1; 
}

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

자료

• 윤성우의 열혈 자료구조 (윤성우 저, 2023.10)