우선순위 큐(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)

저작자표시 비영리 변경금지

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

	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 삭제
	// 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;
	}

1. 우선순위 큐의 이해

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

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

1.3. 힙(heap)의 소개

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

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

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

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

2.4. 힙의 구현

자료

블로그의 정보

활동하기

공유하기

다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역