[자료구조]우선순위 큐(Priority Queue)와 힙(Heap) 힙의 구현과 우선순위 큐의 완성 9-2-3

제법 쓸만한 수준의 힙: 힙의 변경

앞선 상황들의 문제의 해결을 위한 요구사항을 다음 한 문장으로 정리할 수 있다.

프로그래머가 우선순위의 판단 기준을 힙에 설정할 수 있어야 합니다.

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

가장 큰 변화는 구조체 HeapElem 이 사라진 점이다.
우선순위와 데이터를 묶기위해 만든것이기에 우선순위를 맴버에서 없앴기 때문에 더이상 필요하지가 않다.
대신 new member를 추가했다.

PriorityComp *comp; // typedef int (*PriorityComp)(HData d1,HData d2);

이는 함수 포인터 변수이다.

두 개의 데이터 대상으로 우선순위 비교하는 함수를 등록하기 위한 포인터 변수이다.
따라서 이 함수를 정의하는 방법에 대한 가이드라인이 제시 되어야한다.

typedef int (*PriorityComp)(HData d1,HData d2);

• 첫 번째 인자의 우선순위가 높다면, 0보다 큰 값이 반환되도록 정의한다.
• 두 번째 인자의 우선순위가 높다면, 0 보다 작은 값이 반환되도록 정의한다.
• 첫 번째, 두 번째 인자의 우선순위가 동일하다면 0이 반환되도록 정의한다.

이제 위의 내용을 근거로, 프로그래머는 데이터간 우선순위의 비교에 사용될 함수를 정의해서 힙에 등록해야 한다.
따라서 힙의 초기화 함수는 다음과 같이 수정되어야 한다.

void HeapInit(Heap * ph, int idx) // 힙의 초기화
{
    ph->numOfData = 0;
    ph->comp = pc;
}

이제 변경상항들을 완성해보자.
UsefulHeap.h

//
//  UsefulHeap.h
//  UsefulHeap
//
//  Created by 서희찬 on 2021/04/11.
//

#ifndef UsefulHeap_h
#define UsefulHeap_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 /* UsefulHeap_h */

이후 소스파일을 보자
UsefulHeap.c

//
//  UsefulHeap.c
//  UsefulHeap
//
//  Created by 서희찬 on 2021/04/11.
//

#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->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; // 새 노드가 저장될 인덱스 값을 idx에 저
    
    // 새 노드가 저장될 위치가 루트 노드의 위치가 아니라면 while문 반복
    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]; // 힙의 마지막 노드 저장
    
    // parentIdx 에는 마지막 노드가 저장될 위치정보가 담긴다.
    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; // 마지막 노드가 저장될 위치정보를 한 레벨 내림
        // 반복문 탈출하면 parentIdx에는 마지막 노드의 위치정보가 저장된다.
    }
    ph->heapArr[parentIdx] = lastElem; // 마지막 노드 최종 저장
    ph->numOfData-=1;
    return retData;
}

이제 메인을 보자
main.c

//
//  main.c
//  UsefulHeap
//
//  Created by 서희찬 on 2021/04/11.
//

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

int DataPriorityComp(char ch1, char ch2)
{
    return ch2 - ch1;
}
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;
}

다음 함수를 보자

int DataPriorityComp(char ch1, char ch2)
{
    return ch2 - ch1;
}

• 첫 번째 인자의 우선순위가 높다면, 0보다 큰 값이 반환되도록 정의한다.
• 두 번째 인자의 우선순위가 높다면, 0 보다 작은 값이 반환되도록 정의한다.
• 첫 번째, 두 번째 인자의 우선순위가 동일하다면 0이 반환되도록 정의한다.

즉, "아스키 코드 값이 작은 문자의 우선순위가 더 높다" 인것을 알 수 있다. A의 우선순의 가 제일 높고 Z의 우선순위가 제일 낮은 셈이다.

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

우선순위 큐를 고려하여 힙을 구현했기 때문에 사실상 우선순위 큐를 구현한것이 다름없어서 이야기의 시작은 우선순위 큐로 하지만... 힙을 구현하고 끝내는 경우가 다반사다.
하지만! 우리는 마무리를 하자 !
먼저 우선순위 큐의 ADT를 정의하자!

우선순위 큐의 ADT

void PQueueInit(PQueue * ppq, PriorityComp pc);
 - 우선순위 큐의 초기화를 진행한다.
 - 우선순위 큐 생성후 제일 먼저 호출되어야 하는 함수이다.

int PQIsEmpty(PQueue * ppq);
 - 우선순위 큐가 빈 경우 True(1) 그렇지 않은 경우 FALSE(0) 을 반환한다.template

void PEnqueue(PQueue * pqq, PQData data);
 - 우선순위 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.template

PQData PDequeue(PQueue * ppq);
 - 우선순위가 가장 높은 데이터를 삭제한다.
 - 삭제된 데이터는 반환된다.
 - 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야한다.

이어서하고싶지만... 그냥 다음 페이지로 가서 하자 !