우선순위가 높은 데이터가 먼저 나온다
데이터를 근거로 우선순위를 판단할 수 있어야 한다
힙 : 완전 이진 트리. 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 크거나 같아 루트 노드가 가장 큰 값을 저장하는 트리.
heap : 무엇인가를 차곡차곡 쌓아 올린 더미
자식 노드 데이터의 우선순위 <= 부모 노드 데이터의 우선순위
마지막 노드를 루트 노드의 자리로 옮긴 다음에, 자식 노드와의 비교를 통해서 제자리를 찾아가게 한다
힙을 이용하면 트리의 높이에 해당하는 수만큼만 연산을 하면 된다
배열을 기반으로 한다.
연결리스트를 기반으로 구현하면, 새로운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않다
노드에 고유한 번호를 부여한다. 그리고 그 번호가 각 노드의 데이터가 저장 될 배열의 인덱스 값이 된다
#ifndef __SIMPLE_HEAP_H__
#define __SIMPLE_HEAP_H__
#define TRUE 1
#define FALSE 0
#define HEAP_LEN 100
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
#include "SimpleHeap.h"
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;
HeapElem nelem = {pr, data};
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];
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;
}
GetHiPriChildIDX : 두 자식 노드 중에서 우선순위가 높은 것의 인덱스 값을 반환한다.
자식 노드가 없으면 0을 반환하고 하나인 경우에는 그 노드의 인덱스 값을 반환한다.
하나뿐인 자식노드는 왼쪽 자식 노드이고, 힙의 마지막 노드이다.
HDelete : 힙의 마지막 노드를 루트 노드의 위치에 옮긴 다음에, 자식 노드와의 비교 과정을 거치면서 아래로 내린다. 자신의 위치를 찾을 때까지 내린다.
HInsert : 새로운 데이터는 우선 순위가 가장 낮다는 가정 하에서 마지막 위치에 저장한다. 우선순위의 비교를 통해서 자신의 위치를 찾을 때까지 위로 올린다.
프로그래머가 우선순위의 판단 기준을 힙에 설정할 수 있어야 한다.
typedef struct _heap
{
PriorityComp *comp;
int numOfData;
HData heapArr[HEAP_LEN];
} Heap;
PriorityComp
typedef int PriorityComp(HData d1, HData d2);
변경해야 하는 함수
int GetHiPriChildIDX(Heap *ph, int idx);
void HInsert(Heap *ph, HData data);
HData HDelete(Heap *ph);
GetHiPriChildIDX
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);
}
}
HInsert
void HInsert(Heap *ph, HData data)
{
int idx = ph->numOfData+1;
where(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;
}
HDelete
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 -= 1;
return retData;
}
우선순위 큐 자료구조의 ADT
void PQueueInit(PQueue *ppq, PriorityComp pc);
- 우선순위 큐의 초기화를 진행한다
- 우선순위 큐 생성 후 제일 먼저 호출되어야 하는 함수이다
int PQIsEMpty(PQueue *ppq);
- 우선순위 큐가 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다
void PEnqueue(PQueue *ppq, *PQData data);
- 우선순위 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.
PQData PDequeue(PQueue *ppq);
- 우선순위가 가장 높은 데이터를 삭제한다
- 삭제된 데이터는 반환된다
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다
#ifndef __PRIORITY_QUEUE_H__
#define __PRIORITY_QUEUE_H__
#include "UsefulHeap.h"
typedef Heap PQueue;
typedef HData PQData;
void PQueueInit(PQueue *ppq, PriorityComp pc);
int PQIsEmpty(PQueue *ppq);
void PEnqueue(PQueue * ppq, PQData data);
PQData PDequeue(PQueue *ppq);
#endif
#include "PriorityQueue.h"
#include "UsefulHeap.h"
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 PDenqueue(PQueue *ppq)
{
return HDelete(ppq);
}