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

08-1 트리의 개요

스택, 큐와 같은 선형 자료구조들과 달리 트리는 비선형 자료구조이다.

트리(Tree)의 접근

"트리는 계층적 관계(Hierarchical

출처: http://ohdumak.tistory.com/ [오두막]

2018/01/15 - [프로그래밍/자료구조] - Chapter08 트리(Tree)

09-1 우선순위 큐의 이해

제목만 봐서는 앞서 구현한 '큐'를 확장하는 수준 같지만 '큐'의 구현과 '우선순위 큐

'의 구현에는 많은 차이가 있기 때문이다.

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

앞서  공부한 '큐'의 핵심 연산 두 가지

- enqueue 큐에 데이터를 삽입하는 행위

- dequeue 큐에서 데이터를 꺼내는 행위

'우선순위 큐'의 핵심 연산

- enqueue 우선순위 큐에 데이터를 삽입하는 행위

- deququ 우선순위 큐에서 데이터를 꺼내는 행위

"들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다"

우선순위 큐의 구현 방법

- 배열을 기반으로 구현하는 방법

- 연결 리스트를 기반으로 구현하는 방법

- 힙(heap)을 이용하는 방법

"삽입의 위치를 찾기 위해서 첫 번째 노드에서부터 시작해서 마지막 노드에 저장된 데이터와 우선순위의 비교를 진행해야 할 수도 있다."

그래서 우선순위 큐는 단순 배열도 연결 리스트도 아닌 '힙'이라는 자료구조를 이용해서 구현하는 것이 일반적이다.

힙(Heap)의 소개

"힙은 '이진 트리'이되 '완전 이진 트리'이다. 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉 로투 노드에 저장된 값이 가장 커야 한다."

- 최대 힙(max heap): 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리

- 최소 힙(min heap): 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리

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

힙은 우선순위 큐의 구현에 어울리는 완전 이진 트리의 일종이다.

힙에서의 데이터 저장과정

"새로운 데이터는 우선순위가 제일 낮다는 가정하에서 '마지막 위치'에 저장합니다. 그리고는 부모 노드와 우선순위를 비교해서 바뀌어야 한다면 바꿔준다. 바뀐 다음에도 제대로된 위치를 찾을 때까지 계속해서 부모 노드와 비교한다."

데이터의 추가과정은 마지막 위치에 데이터를 두고서 부모 노드와의 비료를 통해 자신의 위치를 찾아가는 매우 단순한 방식이다.

힙에서의 데이터 삭제과정

"마지막 노드를 루트 노드의 자리로 옮긴 다음에, 자식 노드와의 비교를 통해서 제자리를 찾아가게 한다."

삽입과 삭제의 과정에서 보인 성능의 평가

- 배열 기반 데이터 저장의 시간 복잡도 O(n)

- 배열 기반 데이터 삭제의 시간 복잡도 O(1)

- 연결 리스트 기반 데이터 저장의 시간 복잡도 O(n)

- 연결 리스트 기반 데이터 삭제의 시간 복잡도 O(1)

- 힙 기반 데이터 저장의 시간 복잡도 O(log2n)

- 힙 기반 데이터 삭제의 시간 복잡도 O(log2n)

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

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

힙의 구현은 배열을 기반으로 구현하는 것이 원칙이다.

배열을 기본으로 힙을 구현하는데 필요한 지식들

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

- 왼쪽 자식 노드의 인덱스 값: 부모 노드의 인덱스 값 X 2

- 오른쪽 자식 노드의 인덱스 값: 부모 노드의 인덱스 값 X 2 + 1

- 부모 노드의 인덱스 값: 자식 노드의 인덱스 값 / 2

원리 이해 중심의 힙 구현: 헤더파일의 소개

SimpleHeap.h

#ifndef DATASTRUCTURES_HEAP_SIMPLEHEAP_H_
#define DATASTRUCTURES_HEAP_SIMPLEHEAP_H_

/*---- INCLUDES      --------------------------------------------------------*/

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/
#define TRUE		1
#define FALSE		0

#define HEAP_LEN	100

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
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);

#endif /* DATASTRUCTURES_HEAP_SIMPLEHEAP_H_ */

원리 이해 중심의 힙 구현: HDelete 함수에 대한 설명 중심으로

- 힙은 완전 이진 트리이다.

- 힙의 구현은 배열을 기반으로 하며 인덱스가 0인 요소는 비워둔다.

- 따라서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다.

- 노드의 고유번호가 노드가 저장되는 배열의 인덱스 값이 된다.

- 우선순위를 나타내는 정수 값이 작을수록 높은 우선선위를 나타내다고 가정한다.

원리 이해 중심의 힙 구현: HInsert 함수에 대한 설명 중심으로

- 새로운 데이터는 우선순위가 제일 낮다는 가정하에서 '마지막 위치'에 저장

- 우선순위의 비교를 통해서 자신의 위치를 찾을 때까지 위로 올린다.

SimpleHeap.c

/*---- INCLUDES      --------------------------------------------------------*/
#include "SimpleHeap.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
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);
		}
	}
}

// 힙에 데이터 저장
void HInsert(Heap *ph, HData data, Priority pr) {
	int idx = ph->numOfData + 1;	// 새 노드가 저장될 인텍스 값을 idx에 저장
	HeapElem nelem = {pr, data};	// 새 노드의 생성 및 초기화

	// 새 노드가 저장될 위치가 루트 노드의 위치가 아니라면 while문 반복
	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;	// 반환을 위해서 삭제할 데이터 저장
	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;	// 마지막 노드가 저장될 위치정보를 한 레벨 내림
	} // 반복문 탈출하면 parentIdx에는 마지막 노드의 위치정보가 저장됨

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

완성한 힙의 실행을 위한 main 함수! 그리고 반성!

SimpleHeapMain.c

/*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>
#include "SimpleHeap.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
int main(void) {
	Heap heap;
	HeapInit(&heap);					// 힙의 초기화

	HInsert(&heap, 'A', 1);				// 문자 'A'를 최고의 우선순위로 저장
	HInsert(&heap, 'B', 2);				// 문자 'B'를 두 번째 우선순위로 저장
	HInsert(&heap, 'C', 3);				// 문자 'C'를 세 번째 우선순위로 저장
	printf("%C \n", HDelete(&heap));

	HInsert(&heap, 'A', 1);				// 문자 'A' 한 번 더 저장
	HInsert(&heap, 'B', 2);				// 문자 'B' 한 번 더 저장
	HInsert(&heap, 'C', 3);				// 문자 'C' 한 번 더 저장
	printf("%C \n", HDelete(&heap));

	while(!HInsert(&heap)) {
		printf("%C \n", HDelete(&heap));
	}

	return 0;
}

제법 쓸만한 수준의 힙 구현: 힙의 변경

typedef struct _heap {

PriorityComp *comp;

int numOfData;

HData heapArr[HEAP_LEN];

} Heap;

UsefulHeap.h

#ifndef DATASTRUCTURES_HEAP_USEFULHEAP_H_
#define DATASTRUCTURES_HEAP_USEFULHEAP_H_

/*---- INCLUDES      --------------------------------------------------------*/

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/
#define TRUE		1
#define FALSE		0

#define HEAP_LEN	100

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

typedef struct _heap {
	PriorityComp *comp;
	int numOfData;
	HData heapArr[HEAP_LEN];
} Heap;

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
void HeapInit(Heap *ph, PriorityComp pc);
int HIsEmpty(Heap *ph);

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

#endif /* DATASTRUCTURES_HEAP_USEFULHEAP_H_ */

UsefulHeap.c

/*---- INCLUDES      --------------------------------------------------------*/
#include "UsefulHeap.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
void HeapInit(Heap *ph, PriorityComp pc) {
	ph->numOfData = 0;
	ph->comp = pc;
}

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->comp(ph->heapArr[GetLChildIDX(idx)], ph->heapArr[GetRChildIDX(idx)]) < 0) {
			return GetRChildIDX(idx);
		} else {
			return GetLChildIDX(idx);
		}
	}
}

// 힙에 데이터 저장
void HInsert(Heap *ph, HData data) {
	int idx = ph->numOfData + 1;	// 새 노드가 저장될 인텍스 값을 idx에 저장

	// 새 노드가 저장될 위치가 루트 노드의 위치가 아니라면 while문 반복
	while(idx != 1) {
		// 새 노드와 부모 노드의 우선순위 비교
//		if(pr < (ph->heapArr[GetParentIDX(idx)].pr)) { // 새 노드의 우선순위가 높다면
		if(ph->comp(data, ph->heapArr[GetParentIDX(idx)]) > 0) {
			// 부모 노드를 한 레벨 내림, 실제로 내림
			ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
			// 새 노드를 한 레벨 올림, 실제로 올리지는 않고 인덱스 값만 갱신
			idx = GetParentIDX(idx);
		} else {
			break; // 새 노드의 우선 순위가 높지 않다면
		}
	}
	ph->heapArr[idx] = data;	// 새 노드를 배열에 저장
	ph->numOfData += 1;
}

// 힙에서 데이터 삭제
HData HDelete(Heap *ph) {
	HData retData = ph->heapArr[1];	// 반환을 위해서 삭제할 데이터 저장
	HData 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;	// 마지막 노드가 저장될 위치정보를 한 레벨 내림
	} // 반복문 탈출하면 parentIdx에는 마지막 노드의 위치정보가 저장됨

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

UsefulHeapMain.c

/*---- INCLUDES      --------------------------------------------------------*/
#include <stdio.h>
#include "UsefulHeap.h"

/*---- GLOBAL DEF/VAR -------------------------------------------------------*/

/*---- CLASS/FUNC DECLARATION -----------------------------------------------*/
int DataPriorityComp(char ch1, char ch2) {	// 우선순쉬 비교함수
	return ch2 - ch1;
//	return ch1 - ch2;
}
int main(void) {
	Heap heap;
	HeapInit(&heap, DataPriorityComp);		// 우선순위 비교함수 등록

	HInsert(&heap, 'A');
	HInsert(&heap, 'B');
	HInsert(&heap, 'C');
	printf("%C \n", HDelete(&heap));

	HInsert(&heap, 'A');
	HInsert(&heap, 'B');
	HInsert(&heap, 'C');
	printf("%C \n", HDelete(&heap));

	while(!HIsEmpty(&heap)) {
		printf("%C \n", HDelete(&heap));
	}

	return 0;
}

우선순위 큐를 고려하여 힙을 구현했기 때문에 사실상 우선순위 큐를 구현한 것이나 다름 없다.