09장 우선순위 큐(Priority Queue) – 힙(Heap) 이용

Posted on: 2019년 04월 07일 2019년 04월 07일
Categories: 강의자료, 자료구조

용어
1. 우선순위 큐(Priority Queue)
  1. 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.
  2. 우선순위 큐의 구현 방법
    1. 배열을 기반으로 구현
    2. 연결 리스트를 기반으로 구현
    3. 힙(Heap)을 이용하여 구현
2. 힙(Heap)
  1. 이진트리(Binary Tree) 중 완전이진트리(Complete Binary Tree)
  2. 최소힙(Min Heap) : 각 노드는 자식의 값보다 작아야 한다.
  3. 최대힙(Max Heap) : 각 노드는 자식의 값보다 커야 한다.
힙의 연산

출처: https://blog.naver.com/taeil34/221349440884
1. 값 추가 : 맨 마지막 노드에 값을 추가하고 힙을 재구성
  1. 15, 32, 28, 48 순으로 4개를 추가하는 과정 설명
2. 값 삭제 : 루트 노드 값 삭제하고 맨 마지막 노드의 값을 루트 노드로 이동후 힙을 재구성
  1. 값을 3개 삭제하는 과정 설명
우선순위 큐의 시간복잡도
1. 배열 기반 구현
  1. 저장 : O(n)
  2. 삭제 : O(1)
2. 연결 리스트 기반 구현
  1. 저장 : O(n)
  2. 삭제 : O(1)
3. 힙 기반 구현
  1. 저장 : O(log n)
  2. 삭제 : O(log n)
힙의 구현
1. 힙은 트리와 같기 때문에 배열과 연결리스트 모두 구현 가능
2. 배열로 구현해야 함
3. 연결리스트는 마지막 노드를 구하기가 어렵기 때문에 구현 힘듬

배열을 이용한 단순 힙(Heap) : S009_SimpleHeap.c

#include <stdio.h>

#define TRUE	1
#define FALSE	0

#define HEAP_LEN	100

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

int numOfData;
HeapElem heap[HEAP_LEN];

void HeapInit(){
	numOfData = 0;
}

int HIsEmpty(){
	if(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(int idx){
	if(GetLChildIDX(idx) > numOfData){    // 자식 노드가 없다면
		return 0;
	}
	else if(GetLChildIDX(idx) == numOfData){    // 왼쪽 자식 노드가 마지막 노드라면
		return GetLChildIDX(idx);
	}
	else{   // 왼쪽 자식 노드와 오른쪽 자식 노드의 우선순위를 비교
		if(heap[GetLChildIDX(idx)].pr > heap[GetRChildIDX(idx)].pr)
			return GetRChildIDX(idx);
		else
			return GetLChildIDX(idx);
	}
}

void HInsert(char data, int pr){//root노드의 idx = 1
	int idx = numOfData + 1;
	HeapElem nelem = {pr, data};

	while(idx != 1){
		if(pr < (heap[GetParentIDX(idx)].pr)){
			heap[idx] = heap[GetParentIDX(idx)];
			idx = GetParentIDX(idx);
		}
		else{
			break;
		}
	}

	heap[idx] = nelem;
	numOfData += 1;
}

char HDelete()
{
	char retData = heap[1].data;    // 삭제할 데이터 임시 저장
	HeapElem lastElem = heap[numOfData];

	int parentIdx = 1;    // 루트 노드의 Index
	int childIdx;

	while(childIdx = GetHiPriChildIDX(parentIdx))
	{
		if(lastElem.pr <= heap[childIdx].pr)
			break;

		heap[parentIdx] = heap[childIdx];
		parentIdx = childIdx;
	}

	heap[parentIdx] = lastElem;
	numOfData -= 1;
	return retData;
}

int main(void)
{
	HeapInit();

	HInsert('A', 1);
	HInsert('B', 2);
	HInsert('C', 3);
	printf("%c \n", HDelete());

	HInsert('D', 1);
	HInsert('E', 2);
	HInsert('F', 3);
	printf("%c \n", HDelete());

	while(!HIsEmpty())
		printf("%c \n", HDelete());

	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

#include <stdio.h>

#define TRUE 1

#define FALSE 0

#define HEAP_LEN 100

typedef struct _heapElem{

int pr; // 값이 작을수록 높은 우선순위

char data;

} HeapElem;

int numOfData;

HeapElem heap[HEAP_LEN];

void HeapInit(){

numOfData = 0;

}

int HIsEmpty(){

if(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(int idx){

if(GetLChildIDX(idx) > numOfData){ // 자식 노드가 없다면

return 0;

}

else if(GetLChildIDX(idx) == numOfData){ // 왼쪽 자식 노드가 마지막 노드라면

return GetLChildIDX(idx);

}

else{ // 왼쪽 자식 노드와 오른쪽 자식 노드의 우선순위를 비교

if(heap[GetLChildIDX(idx)].pr > heap[GetRChildIDX(idx)].pr)

return GetRChildIDX(idx);

else

return GetLChildIDX(idx);

}

void HInsert(char data, int pr){//root노드의 idx = 1

int idx = numOfData + 1;

HeapElem nelem = {pr, data};

while(idx != 1){

if(pr < (heap[GetParentIDX(idx)].pr)){

heap[idx] = heap[GetParentIDX(idx)];

idx = GetParentIDX(idx);

}

else{

break;

}

heap[idx] = nelem;

numOfData += 1;

}

char HDelete()

{

char retData = heap[1].data; // 삭제할 데이터 임시 저장

HeapElem lastElem = heap[numOfData];

int parentIdx = 1; // 루트 노드의 Index

int childIdx;

while(childIdx = GetHiPriChildIDX(parentIdx))

{

if(lastElem.pr <= heap[childIdx].pr)

break;

heap[parentIdx] = heap[childIdx];

parentIdx = childIdx;

}

heap[parentIdx] = lastElem;

numOfData -= 1;

return retData;

}

int main(void)

{

HeapInit();

HInsert('A', 1);

HInsert('B', 2);

HInsert('C', 3);

printf("%c \n", HDelete());

HInsert('D', 1);

HInsert('E', 2);

HInsert('F', 3);

printf("%c \n", HDelete());

while(!HIsEmpty())

printf("%c \n", HDelete());

return 0;

}

whan0623

517