9. 우선순위 큐와 힙

※ 해당 글은 C언어에 대한 이해를 필요로 합니다. C 언어에 대해 알고 싶으신 분들은 다음 글을 참고하세요

https://ward.tistory.com/category/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D%20%EC%96%B8%EC%96%B4/C

'프로그래밍 언어/C' 카테고리의 글 목록

 

(1) 우선순위 큐의 이해

 

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

우선순위 큐는 들어간 순서와 상관없이 우선순위가 높은 데이터가 먼저 나온다.

 

* 우선순위 큐의 구현 방법

우선순위 큐를 구현하는 방법은 배열을 이용하는 방법, 연결 리스트를 이용하는 방법, 힙을 이용하는 방법이 있다.

배열 기반 우선순위 큐는 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 한다.

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

따라서 우선순위 큐는 힙을 이용해서 구현하는 것이 일반적이다.

 

* 힙의 소개

힙은 완전 이진 트리이고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 우선순위가 크거나 같다.

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

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

 

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

 

* 힙에서의 데이터 저장과정

새로운 데이터는 우선순위가 제일 낮다는 가정하에 마지막 위치에 저장, 부모 노드와 우선순위를 비교해서 위치가 바뀌어야 한다면 바꾼다. 이 과정을 반복하여 제대로 된 위치를 찾는다.

삽입의 시간복잡도: O(logn)

 

* 힙에서 데이터 삭제과정

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

삭제의 시간복잡도: O(logn)

 

* 힙의 구현 도구

우선순위 큐의 구현에는 힙이 사용된다. 그렇다면 힙의 구현에는 배열을 이용할까 아니면 연결 리스트를 이용할까?

트리는 연결 리스트를 기반으로 구현하므로 힙도 연결 리스트 기반으로 구현한다고 생각할 수 있지만 연결 리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않다. 따라서 힙은 배열을 기반으로 구현한다.

 

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

• 왼쪽 자식 노드의 인덱스 값: 부모 노드의 인덱스 값 * 2
• 오른쪽 자식 노드의 인덱스 값: 부모 노드의 인덱스 값 * 2 + 1
• 부모 노드의 인덱스 값: 자식 노드의 인덱스 값 / 2

* 힙의 구현

#include <stdio.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)
{
	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 i = ph->numOfData + 1;
	while (i != 1) {
		if (ph->comp(data, ph->heapArr[GetParentIDX(i)]) > 0) {
			ph->heapArr[i] = ph->heapArr[GetParentIDX(i)];
			i = GetParentIDX(i);
		}
		else
			break;
	}
	ph->heapArr[i] = data;
	(ph->numOfData)++;
}

HData HDelete(Heap* ph)
{
	HData retData = ph->heapArr[1];
	HData lastElem = ph->heapArr[ph->numOfData];
	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;
	}
	ph->heapArr[parentIdx] = lastElem;
	(ph->numOfData)--;
	return retData;
}

 

* 우선순위 큐의 ADT 정의

Operations:

• void PQueueInit(PQueue* ppq, PriorityComp pc)
  • 우선순위 큐의 초기화를 진행한다.
  • 우선순위 큐 생성 후 제일 먼저 호출되어야 하는 함수이다.
• int PQIsEmpty(PQueue* ppq)
  • 우선순위 큐가 빈 경우 TRUE를, 그렇지 않은 경우 FALSE를 반환한다.
• void PEnqueue(PQueue* ppq, PQData data)
  • 우선순위 큐에 데이터를 저장, 매개변수 data로 전달된 값을 저장한다.
• PQData PDequeue(PQueue* ppq)
  • 우선순위가 가장 높은 데이터를 삭제한다.
  • 삭제된 데이터는 반환한다.
  • 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

* 힙을 이용한 우선순위 큐의 구현

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

typedef Heap PQueue;
typedef HData PQData;

void PQueueInit(PQueue * ppq, PriorityComp pc)
{
	HeapInit(ppq, pc);
}

int PQIsEmpty(PQueue * ppq)
{
	return HIsEmpty(ppq);
}

void PEnqueue(PQueue * ppq, PQData data)
{
	HInsert(ppq, data);
}

PQData PDequeue(PQueue * ppq)
{
	return HDelete(ppq);
}

 

참조문헌: 윤성우의 열혈 자료구조