우선순위 큐

우선순위 큐는 이름 그대로 우선순위를 고려하여 만든 큐이다. 우선순위 큐의 규현 방법에는 '배열, 연결리스트, 힙' 으로 총 3가지가 있다. 이 중에서 우선순위 큐는 힙으로 구현하는게 가장 효율이 좋다. 그 이유는 배열과 연결리스트의 경우 데이터의 추가, 삭제의 시간 복잡도가 O(n)인 반면, 힙의 경우에는 추가, 삭제의 시간 복잡도가 log2(n)이기 때문이다. 

 

힙은 배열과 연결리스트 중에서 배열로 구현을 한다. 그 이유는 연결리스트로 구현을 하면 새로운 노드를 마지막 위치에 추가하기가 쉽지 않기 때문이다. 

힙에서의 데이터 저장과정

위 그림을 보면 새로운 데이터를 마지막 위치에 저장한 후 부모 노드와 비교연산을 통해 제자리를 찾아가는 것을 알 수 있다.

힙에서의 데이터 삭제과정

위 그림을 보면 우선순위가 가장 높은 데이터가 위치한 루트 노드이 데이터를 삭제한 후 가장 마지막의 위치한 데이터를 루트노드로 올려 자식 노드와 비교연산을 통해 제자리를 찾아가는 것을 알 수 있다.

힙의 구현

헤더파일

#ifndef __USEFUL_HEAP_H__
#define __USEFUL_HEAP_H__

#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;

void HeapInit(Heap * ph, PriorityComp pc);
int HIsEmpty(Heap * ph);

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

#endif

소스파일

#include "UsefulHeap.h"

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;

	while(idx != 1)
	{
		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(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;
}

메인파일

#include <stdio.h>
#include "UsefulHeap.h"

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;
}

이제 이 힙을 활용하여 Enqueue, Dequeue 연산을 해 주면 된다.

 

 

 

---------------------------------------------------

이 글은 윤성우의 열혈 자료구조를 읽고 정리한 글 입니다.