배열을 기반으로 힙을 구현하는데 필요한 지식들
"노드에 고유의 번호를 부여한다. 그리고 그 번호가 각 노드의 데이터가 저장 될 배열의 인덱스 값이 된다."
위 그림에서 보이듯이 , 구현의 편의를 위해서 인덱스가 0인 위치의 배열 요소는 사용하지 않는다는 사실도 앞서 언급하였다. 그럼 배열을 기반으로 힙을 구현하기 위해서 무엇을 더 알아야 할까?
"왼쪽 그리고 오른쪽 자식 노드의 인덱스 값을 얻는 방법, 그리고 부모 노드의 인덱스 값을얻는 방법"
자식 노드의 인덱스 값을 얻는 방법은 데이터의 삭제를 위해서, 부모 노드의 인덱스 값을 얻는 방법은 데이터의 추가를 위해서 필요하다. 그럼 이 두가지 방법을 소개하겠다.
왼쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 x 2
오른쪽 자식 노드의 인덱스 값 : 부모 노드의 인덱스 값 x 2 +1
부모 노드의 인덱스 값 : 자식 노드의 인덱스 값 / 2
의외로 간단하다. 이진 트리는 레벨이 증가함에 따라서 추가할 수 있는 자식 노드의 수가 두 배씩 증가하는 구조다 보니, 2를 나누고 곱하는 방식으로 부모 노드와 자식 노드의 인덱스 값을 구할 수 있다. 실제로 위의 식이 맞는지 앞서 보인 그림을 대상으로 확인하기 바란다. 그리고 한가지 주의할 점은 , 부모 노드의 인덱스 값을 구하기 위한 나눗셈 연산은 정수형 나눗셈이라는 점이다. 즉 5를 2로 나누었을 때의 결과는 2.5가 아니라 2가 되어야 한다.
원리 이해 중심의 힙 구현 : 헤더파일의 소개
우선 좋은 모델은 아니나 우리가 이해하기 용이한 방식으로 힙을 구현하겠다. 그리고 이어서 이 모델을 보다 합리적인 형태로 변경하기로 하겠다.
//SimpleHeap.h
#ifndef __SIMPLE_HEAP_H__
#define __SIMPLE_HEAP_H__
#define TRUE 1
#define FALSE 0
#deifne 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사실 위의 헤더파일은 순수한 힙의 구현을 위한 헤더파일이 아닌, 우선순위 큐의 구현을 염두에 두고 정의한 헤더파일이다. 그리고 이 사실은 다음 구조체의 정의에서 느낄수 있다.
typedef struct _heapElem
{
Priority pr; //값이 작을수록 높은 우선순위
HData data;
}HeapElem;
이는 힙에 저장될 데이터의 모델을 정의한 구조체이다. 그런데 이 구조체는 우선순위 정보를 별도로 담을수 있도록 정의되어 있다. 이는 우선순위 큐의 구현을 고려했다는 뜻이다. 따라서 위의 헤더파일에 선언된 HDelete 함수는 우선순위 큐와 마찬가지로, 데이터의 삽입 순서에 상관 없이 우선순위에 근거하여 삭제가 이뤄지도록 정의한 것이다.
원리 이해 중심의 힙 구현 : HDelete 함수에 대한 설명 중심으로
이어서 헤더파일에 선언된 함수들의 정의를 보이겠다. 그런데 이를 보기에 앞서 다음 사실들을 정리하고 기억할 필요가 있다.
힙은 완전 이진 트리이다.
힙의 구현은 배열을 기반으로 하며 인덱스가 0인 요소는 비워둔다.
따라서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호는 일치한다.
노드의 고유번호가 노드가 저장되는 배열의 인덱스 값이 된다.
우선순위를 나타내는 정수 값이 작을수록 높은 우선순위를 나타낸다고 가정한다.
이 중에서 힙에 저장된 노드의 개수와 마지막 노드의 고유번호가 일치한다는 사실을 제외하면 나머지는 앞서 언급한 것들이다. 그리고 노드의 개수와 마지막 노드의 고유번호가 일치하는 이유는 우리도 잘 알것이다.
이제 아래의 코드를 분석해보자.
//SimpleHeap.c
#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->headArr[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 함수의 구현에 대한 설명이 필요할 것같다. 우선 이 함수의 기능 및 역할을 정리해 보겠다.
"함수 GetHiPriChildIDX에 노드의 인덱스 값을 전달하면, 이 노드의 두 자식 노드 중에서 우선순위가 높은 것의 인덱스 값을 반환한다."
"함수 GetHiPriChildIDX는 인자로 전달된 노드에 자식 노드가 없으면 0을 반환하고, 자식 노드가 하나인 경우에는 그 노드의 인덱스 값을 반환한다."
이제 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->heapArr[GetLChildIDX(idx)].pr > ph->heapArr[GetRChildIDX(idx)].pr)
return GetRChildIDX(idx); //오른쪽 자식 노드의 인덱스 값 반환
//왼쪽 자식 노드의 우선순위가 높다면,
else
return GetLChildIDX(idx); //왼쪽 자식 노드의 인덱스 값 반환
}
}
위의 함수에서는 자식 노드가 하나도 존재하지 않는 상황을 다음의 연산문을 통해서 확인하고 있는데 이 부분이 잘 이해되지 않을 수 있다.
if(GetLChildIDX(idx) > ph->numOfData) //자식 노드가 없다면 TRUE
return 0;
힙은 완전 이진 트리이므로 오른쪽 자식 노드만 존재하는 상황은 발생하지 않는다. 따라서 왼쪽 자식 노드가 없다면 자식 노드가 존재하지 않는 것으로 판단할 수 있다. 그리고 힙은 완전 이진 트리이므로 다음과 같은 특성이 있다.
"자식 노드가 하나도 존재하지 않는 노드는 단말 노드입니다."
그런데 단말 노드의 왼쪽 자식 노드의 인덱스 값은 힙에 저장된 노드의 수를 넘어선다. 단말 노드의 왼쪽 자식 노드는 존재하지 않으니 말이다. 그래서 위의 연산문으로 자식 노드의 유무를 확인할 수 있는 것이다.
그럼 이번에는 자식 노드가 하나만 존재하는 경우를 판단하기 위한 다음 연산문을 보자. 위의 설명을 잘 이해 했다면 이 연산문도 이해가 될 것이다.
else if (GetLChildIDX(idx) == ph->numOfData) //자식 노드가 하나라면 TRUE
return GetLChildIDX(idx);
반복되는 말이지만, 힙은 완전 이진 트리 이므로 하나 뿐인 자식 노드는 다음의 특징을 갖는다.
"하나뿐인 자식 노드는 왼쪽 자식 노드이다. 그리고 힙의 마지막 노드이다."
따라서 위의 연산문을 통해서 자식 노드가 하나인 상황을 판별할 수 있는 것이다.
그럼 지금 설명한 GetHiPriChildIDX 함수와 관련이 잇는 HDelete함수를 소개하겠다. 참고로 HInsert함수를 소개하는 것이 먼저라 생각할 수 있지만, 앞서 우리는 삽입과 삭제의 방법을 모두 정리했으므로 순서는 상관없을 것이다.
HDelete 함수의 구현 부를 보기 이전에, 앞서 그림을 통해 설명한 노드의 삭제 과정을 다시 한번 보자. 그러면 다음사실을 파악할 수 있다.
"힙의 마지막 노드를 루트 노드의 위치에 올린 다음에, 자식 노드와의 비교과정을 거치면서 아래로 내린다. 자신의 위치를 찾을 때 까지 내린다."
따라서 우리는 다음과 같이 판단할 수 있다.
"루트 노드로 올려진 마지막 노드는 자신의 위치를 찾을 때 까지 아래로 이동하면서 자신의 위치를 찾아간다. 하지만 이러한 빈번한 이동을 코드에 그대로 담을 필요는 없다. 최종 목적지가 결정되면 단번에 그리로 옮기면 된다."
앞서 보인 HDelete 함수는 이러한 생각을 반영하여 구현하였다. 때문에 그림을 통해서 설명한 삭제의 방법과 차이가 있다고 생각할 수 있지만 사실은 같은 것이다. 그럼 이어서 구현의 이해를 돕는 주석을 포함하여 HDelete 함수를 다시 한번 보이겠다.
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;
}
위의 함수에서 다음 사실만 파악하면 앞서 그림을 통해 설명한 삭제의 과정과 '사실상 같은 것'이 아니라 '그냥 가틍ㄴ 것'임을 알 수 있을 것이다.
"함수 HDelete 에서는 마지막 노드가 있어야 할 위치를 parentIdx에 저장된 인덱스 값을 갱신해가며 찾아가고 있다."
HDelete 함수가 호출되면서 변수 parentIdx는 1로 초기화 된다. 그런데 1은 루트 노드의 인덱스 값이므로, 변수 parentIdx가 1로 초기화 된 이 상황을 마지막 노드를 루트 노드로 옮긴 상황으로 간주할 수 있다.
그리고 while반복문의 끝에 위치한 다음 두 문장의 실행은, 루트 노드로 옮겨진 마지막 노드와 우선순위가 높은 자식 노드와의 교환이 이뤄지는 상황으로 간주할 수 있다.
//childIdx에 위치한 노드를 부모 노드의 위치로 올림, 실제로 올린다.
ph->heapArr[parentIdx] = ph->heapArr[childIdx];
//parentIdx에 위치한 노드를 자식 노드의 위치로 내림, 실제로 내리진 않는다.
parentIdx= childIdx;
원리 이해 중심의 힙 구현 : HInsert함수에 대한 설명 중심으로
HDelete 함수의 정의를 이해하면, HInsert 함수는 쉽게 이해할 수 있다. 유사한 성격의 함수이기 때문이다.
그럼 앞서 설명한 삽입의 과정을 정리해 보자.
"새로운 데이터는 우선순위가 제일 낮다는 가정하에서 '마지막 위치'에 저장한다. 그리고는 우선순위의 비교를 통해서 자신의 위치를 찾을 때 까지 위로 올린다."
HDelete 함수를 구현할 때와 마찬가지로 HInsert함수를 구현할 때에도 , 새로운 데이터가 담긴 노드를 이리저리 이동시킬 필요가 없다. 새로운 노드가 있어야 할 위치의 인덱스 값만 유지를 해도 된다. 그럼 주석을 포함한 함수의 정의를 보이겠다.
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;
}
위의 함수에서도 새로운 노드가 저장되어야 할 위치 정보를 변수 idx를 통해서 계속 갱신해 나가고 있다. 따라서 앞서 그림을 통해서 설명한 노드의 삽입 과정을 그대로 코드로 옮긴 것으로 볼 수 있다.
완성한 힙의 실행을 위한 main함수
완성된 힙의 테스트를 위한 main함수와 그 실행결과를 보이겠다. 그리고 나서 개선할 부분에 대해 논의해보자.
//SimpleHeapMain.c
#include <stdio.h>
#include "SimpleHeap.h"
int main()
{
Heap heap;
HeapInit(&heap); //힙의 초기화
HInsert(&heap, 'A', 1);
HInsert(&heap, 'B', 2);
HInsert(&heap, 'C', 3);
printf("%c \n", HDelete(&heap));
HInsert(&heap, 'A', 1);
HInsert(&heap, 'B', 2);
HInsert(&heap, 'C', 3);
printf("%c \n", HDelete(&heap));
while(!HisEmpty(&heap))
printf("%c\n", HDelete(&heap));
return 0;
}
================================실행결과============================
A
A
B
B
C
C
실행결과는 우선순위가 높은 문자들이 먼저 꺼내졌음을 증명하고 있다. 그렇다면 우리가 구현한 위의 힙이 좋은 평가를 받은만한 수준인가? 우리가 구현한 힙이 딱 어울릴만한 상황에서는 좋은 평가를 기대할수도 있다. 하지만 일반적인 상황에서도 좋은 평가를 기대하기는 몇가지 부족한 점이 존재한다. 그리고 그 부족한 점을 다음 구조체의 정의에서 우선 발견할 수 있다.
typedef struct _heapElem
{
Priority pr; //typedef int Priority
HData data; //typedef char HData;
}HeapElem;
위의 구조체는 힙을 이루는 노드를 표현한 것인데, 이 구조체의 멤버로 우선순위 정보를 담는 변수가 선언되어 있다. 바로 이것이 문제로 지적될 수 있는 부분이다. 그럼 이번에는 문제로 지적될 수 있는 또 다른 함수의 선언을 보이겠다.
void HInsert(Heap * ph, HData data, Priority pr); //우선 순위 정보도 넘겨라
이러한 함수의 선언이 뜻하는 바는 다음과 가탇. 함수가 다음과 같이 이야기하는 것과 다름이 없다.
"데이터를 입력하기 전에 우리가 알아서 우선위를 결정하고 그 값을 전달해"
이러한 종류의 문제를 근본적으로 해결하기 위해서는 우리가 구현한 힙을 어떻게 바꿔야 할까?
제법 쓸만한 수준의 힙 구현 : 힙의 변경
앞서 구현한 힙의 문제점을 이해했는가? 그럼 그 문제의 해결을 위한 요구사항을 다음 한 문장으로 정리할 수 있다.
"프로그래머가 우선순위의 판단 기준을 힙에 설정할 수 있어야 한다."
프로그래머가 우선순위의 판단 기준을 힙에 설정할 수 있다는 것은 , 힙의 적용 범위와 활용 방법이 넓어짐을 의미한다. 따라서 우리는 앞서 힙의 구현을 위한 구조체를 다음과 같이 정의하였는데,
typedef struct _heapElem
{
Priority pr;
Hdata data;
}HeapElem;
typedef struct _heap
{
int numOfData;
HeapElem heapArr[HEAP_LEN];
}Heap;
우선순위의 판단 기준을 힙에 설정할 수 있어야 한다는 요구사항을 만족하기 위해서, 이 둘은 다음과 같이 하나의 구조체로 대신하고자 한다.
typedef struct _heap
{
PriorityComp * comp; //typedef int (*PriorityComp)(HData d1, HData d2);
int numOfData;
HData heapArr[HEAP_LEN]; //typedef char HData;
}Heap;
가장 큰 변화는 구조체 HeapElem이 사라진 점이다. HeapElem은 데이터와 우선순위를 하나로 묶기 위한 구조체였는데, 이 중에서 우선순위를 젖아하는 멤버를 완전히 없앴기 때문에 더이상 HeapElem이 존재할 이유가 사라진 것이다. 대신에 구조체 Heap에는 다음 멤버가 추가되었다.
PriorityComp * comp ; //typedef int (*PriorityComp)(Hdata d1, HData d2);
이는 함수 포인터 변수이다. 두 개의 데이터를 대상으로 우선순위의 높고 낮음을 판단하는 함수를 등록하기 위한 포인터 변수이다. 물론 여기에 등록할 함수는 프로그래머가 직접 정의해야 한다. 따라서 이 함수를 정의하는 방법에 대한 가이드라인이 제시되어야 한다.
다음과 같이 가이드라인을 작성했다.
1. PriorityComp의 typedef 선언은 다음과 같다.
typedef int (*PriorityComp)(HData d1, HData d2);
2. 첫번째 인자의 우선순위가 높다면 , 0보다 큰 값이 반환되도록 정의한다.
3. 두번째 인자의 우선순위가 높다면, 0보다 작은 값이 반환되도록 정의한다.
4. 첫번째, 두번째 우선순위가 동일하다면 0이 반환되도록 정의한다.
위의 typedef 선언은 함수의 반환형과 매개변수의 선언을 어떻게 해야 하는지 알려준다. 이제 프로그래머는 위의 내용을 근거로, 데이터간 우선순위의 비교에 사용될 함수를 정의해서 힙에 등록해야 한다. 따라서 힙의 초기화 함수는 다음과 같이 수정되어야 한다.
void HeapInit(Heap * ph, PriorityComp pc)
{
ph->numOfData = 0;
ph->comp =pc; //우선순위 비교에서 사용되는 함수의 등록
}
더불어, HInsert함수를 호출하면서 우선순위 정보를 직접 전달하지 않기 때문에 이 함수의 원형도 다음과 같이 변경되어야 한다.
void HInsert (Heap * ph, HData data);
이렇게 변경되면 ,프로그래머는 우선순위 값을 직접 계산할 필요가 없다. 그저 요구대로 우선순위를 비교하는, 기준이 되는 함수만 정의해서 등록하면 된다.
제법 쓸만한 수준의 힙 구현 : 힙의 변경사항 완성하기
앞서 지적한 변경사항을 토대로 나머지 부분을 변경하는 일만 남았다. 실제 변경해야 하는 함수는 먼저 소개한 HeapInit을 제외하고 다음 세 함수가 전부이다.
int GetHiPriChildIDX(Heap * ph, int idx);
void HInsert(Heap * ph, HData data);
HData HDelete(Heap *ph);
변경 포인트는 우선순위의 비교를 위해서 사용된, 대소 비교 연산자가 존재하는 문장들이다. 그럼 이어서 변경된 힙의 헤더파일과 소스파일을 소개하겠다.
//UsefulHeap.h
#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);
typdef 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//UsefulHeap.c
#include "UsefulHeap.h"
void HeapInit(Heap *ph, PriorityComp pc)
{
ph->numOfData = 0;
ph->comp = pc;
}
int HIsEmpty(Heap *ph) { 동일 }
int GetParentIDX(int idx) {동 일}
int GetLChildIDX(int idx) {동 일}
int GetRChildIDX(int idx) {동 일}
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)
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(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];
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;
}
ph->heapArr[parentIdx] = lastElem;
ph->numOfData -= 1;
return retData;
}
//UsefulHeapMain.c
#include <stdio.h>
#include "UsefulHeap.h"
int DataPriorityComp(char ch1, char ch2) //우선순위 비교 함수
{
return ch2- ch1;
}
int main()
{
Heap heap;
HeapInit(&heap, DatPriorityComp); // 우선순위 비교함수 등록
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;
}
======================================실행결과==============================
A
A
B
B
C
C위의 소스파일에서 정의되어 있는 다음 함수를 보자.
int DataPriorityComp(char ch1, char ch2)
{
return ch2- ch1; //return ch1- ch2 로 변경하여 실행결과를 확인하자
}
이 함수는 첫번째 인자로 전달된 문자의 아스키 코드 값이 작을 때 0보다 큰값을 반환하도록 정의되었다. 그런데 이 함수를 정의하는 기준을 앞서 다음과 같이 결정하였다.
1. 첫 번째 인자의 우선순위가 높다면 , 0보다 큰 값이 반환되도록 정의한다.
2. 두 번째 인자의 우선순위가 높다면, 0보다 작은 값이 반환되도록 정의한다.
3. 첫번째 , 두번째 인자의 우선순위가 동일하다면, 0이 반환하도록 정의한다.
따라서 이 함수의 우선순위 판단 기준은 다음과 같음을 알 수 있다.
"아스키 코드 값이 작은 문자의 우선순위가 더 높다!"
그런데 알파벳의 아스키 코드 값은 문자 'A'를 시작으로 문자 'Z'까지 1씩 증가하므로, 문자 'A'의 우선순위가 제일 높고 문자 'Z'의 우선순위가 제일 낮은 셈이다. 그리고 이러한 사실은 예제의 실행결과에서도 보여주고 있다.
제법 쓸만한 수준의 힙을 이용한 우선순위 큐의 구현
힙을 완성하였으니 이를 기반으로 우선순위 큐를 구현할 차례이다. 그런데 앞서 말했듯이 우선순위 큐를 고려하여 힙을 구현했기 때문에 사실상 우선순위 큐를 구현한 것이나 다름없다. 실제로 힙의 HInsert, HDelete 함수의 호출결과는 우선순위 큐의 enqueue, dequeue 연산 결과와 일치한다.
먼저 우선순위 큐의 ADT를 정의하고 나서, 앞서 구현한 힙을 활용하여 우선순위 큐를 완성해보자.
우선순위 큐 자료구조의 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);
-우선순위가 가장 높은 데이터를 삭제한다.
-삭제된 데이터는 반환한다.
-본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.
이어서 힙을 기반으로 구현한 우선순위 큐의 헤더파일과 소스파일, 그리고, main함수 까지 소개하면서 우선순위 큐와 힙에 대한 이야기를 마무리 하겠다.
//PriorityQueue.h
#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//PriorityQueue.c
#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 PDequeue(PQueue * ppq)
{
return HDelete(ppq);
}//PriorityQueueMain.c
#include <stdio.h>
#include "PriorityQueue.h"
int DataPriorityComp(char ch1, char ch2)
{
return ch2-ch1;
}
int main()
{
PQueue pq;
PQueueInit(&pq, DataPriorityComp);
PEnqueue(&pq, 'A');
PEnqueue(&pq, 'B');
PEnqueue(&pq, 'C');
printf("%c \n", PDequeue(&pq));
PEnqueue(&pq, 'A');
PEnqueue(&pq, 'B');
PEnqueue(&pq, 'C');
printf("%c \n", PDequeue(&pq));
while(!PQIsEmpty(&pq))
printf("%c \n", PDequeue(&pq));
return 0;
}
======================================실행결과========================
UsefulHeap.h, UsefulHeap.c, PriorityQueue.h, PriorityQueue.c, PriorityQueueMain.c
---------------------------------------------------------------------------------
A
A
B
B
C
C
'휴지통 > 자료구조-C' 카테고리의 다른 글
| 우선순위 큐(Priority Queue) 와 힙(Heap) 1 (0) | 2021.03.07 |
|---|---|
| 트리2 (0) | 2021.03.03 |
| 트리 1 (0) | 2021.03.02 |
| 덱(Deque)의 이해와 구현 (0) | 2021.03.01 |
| 큐(Queue)의 연결리스트 기반 구현 (0) | 2021.02.28 |
