[자료구조]힙의 변경

앞서 구현한 힙은 데이터를 기준으로 우선순위가 결정되는게 아니라  먼저 우리가 결정해서 알려줘야 했다.

원래 우선순위의 판단기준은 데이터 자체로 판단해야 한다.

 

HInsert(&heap,'A',4);

HInsert(&heap,'B',3);

HInsert(&heap,'C',2);

HInsert(&heap,'D',1);

HInsert(&heap,'E',5);

 

이 부분에서 우선순위를 직접 결정해서 함수에 넘겨주었다.

 

이번엔 우선순위 기준을 가진 함수를 만들어 프로그래머가 만든 기준을 바탕으로 데이터의 우선순위를 결정해보자.

 

 

#include<stdio.h>

typedef char HData;
typedef int Priority;

typedef struct _heapElem{
    Priority pr;
    HData data;
}HeapElem;

typedef struct _heap{
    int numofData;  
    HeapElem heapArr[100];  
}Heap;

_heapElem 구조체는 우선순위와 데이터 정보를 담는 구조체이다. 이번엔 데이터의 정보만으로 우선순위를 판단하니 이 구조체는 지우고 우선순위를 판단하는 함수를 만들어주면 되겠다.

 

#include<stdio.h>

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

typedef struct _heap{
    PriorityComp * comp;
    int numofData;  
    HData heapArr[100];  
}Heap;

void HeapInit(Heap * ph,PriorityComp pc){
    ph->numofData = 0;
    ph->comp = pc;
}

 

 

PriorityComp함수 포인터를 이용한다.

comp 포인터 변수를 만들었고, 두 데이터의 우선순위를 판단하는 함수를 담는 변수이다.

그리고 HeapInit에서 이 변수를 pc라는 인자로 받아와 초기화 해준다. pc 자리에는 우선순위를 판단하는 함수가 들어가겠다.

 

다음으로 HInsert함수에서도 수정을 해야한다.

함수 내에서 우선순위를 계산하는 과정이 필요없다.

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){  //우선순위 기준 함수의 결과가 0보다 크면(첫번째 인자의 우선순위가 높다)  
            ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];  //새로 들어올 노드의 자리를 만들고 부모 노드 자리에 위치 시킨다.
            idx = GetParentIDX(idx);    //새로운 노드를 부모자리에 넣기위해 인덱스 저장
        }
        else
            break;
    }
    ph->heapArr[idx] = nelem;   //새로운 노드의 값을 저장한다.
    ph->numofData+=1;   
    
}

 

HDelete함수도 마찬가지로 우선순위 계산 과정을 바꿔주자.

 

HData HDelete(Heap * ph){
    HData retData = ph->heapArr[1];  //부모 노드
    HData lastElem = ph->heapArr[ph->numofData]; 

    int parentIdx = 1;
    int childIdx = GetHiPriChildIDX(ph,parentIdx);  //자리 바꾼 노드와 자식 노드의 우선순위 비교를 위한 childIdx
    
    while(childIdx == GetHiPriChildIDX(ph,parentIdx)){   //왼쪽 노드와 비교,
        //if(lastElem.pr <= ph->heapArr[childIdx].pr) //가장 마지막 노드와 루트 노드 다음으로 우선순위 높은 노드 비교했을 때 마지막 노드의 우선순위가 높다면 
        if(ph->comp(lastElem,ph->heapArr[childIdx]) >= 0)   //우선순위 기준 함수의 결과값이 0보다 크거나 같으면(첫번째 인자의 우선순위가 높거나 같으면)
            break;
        ph->heapArr[parentIdx] = ph->heapArr[childIdx]; //마지막 노드보다 우선순위가 높으니, 비교대상 노드(자식 노드)의 위치정보를 한 레벨 올림
        parentIdx = childIdx;   //인덱스 변경
    }
    
    ph->heapArr[parentIdx] = lastElem;  //마지막 노드의 위치를 최종 변경
    ph->numofData -= 1;
    
    return retData;

}

 

우선순위를 판단하는 함수의 가이드라인은 어떻게 될까?

1.첫번째 인자 HData d1의 우선순위가 높다면, 0보다 큰 값이 반환되도록 한다.

2.두번재 인자 HData d2의 우선순위가 높다면, 0보다 작은 값을 반환되도록 한다.

3.첫번째, 두번째 인자의 우선순위가 동일하다면, 0을 반환되도록 한다.

 

 

#include<stdio.h>

typedef char HData;
typedef int Priority;
typedef int PriorityComp(HData d1,HData d2);

typedef struct _heap{
    PriorityComp * comp;
    int numofData;  
    HData heapArr[100];  
}Heap;

void HeapInit(Heap * ph,PriorityComp pc){
    ph->numofData = 0;
    ph->comp = pc;
}


int HIsEmpty(Heap * ph){
    if(ph->numofData == 0)
        return 1;
    else
        return 0;
}

int GetParentIDX(int idx){
    return idx/2;
}

int GetLChildIDX(int idx){
    return idx*2;
}

int GETRChildIDX(int idx){
    return (idx*2)+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(pr < (ph->heapArr[GetParentIDX(idx)].pr)){   //부모 노드의 우선순위가 새로 들어올 노드의 우선순위보다 클 경우(우선순위가 낮다)
        if(ph->comp(data,ph->heapArr[GetParentIDX(idx)]) > 0){  //우선순위 기준 함수의 결과가 0보다 크면(첫번째 인자의 우선순위가 높다)  
            ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];  //새로 들어올 노드의 자리를 만들고 부모 노드 자리에 위치 시킨다.
            idx = GetParentIDX(idx);    //새로운 노드를 부모자리에 넣기위해 인덱스 저장
        }
        else
            break;
    }
    ph->heapArr[idx] = data;   //새로운 노드의 값을 저장한다.
    ph->numofData+=1;   
    printf("%c is inserted\n",data);
}

HData HDelete(Heap * ph){    
    HData retData = ph->heapArr[1];  //부모 노드
    HData lastElem = ph->heapArr[ph->numofData]; 

    int parentIdx = 1;
    int childIdx = GetHiPriChildIDX(ph,parentIdx);  //자리 바꾼 노드와 자식 노드의 우선순위 비교를 위한 childIdx
    
    if(ph->numofData == 1){             //마지막 노드를 출력해주기 위해
        return ph->heapArr[parentIdx]; 
    }

    while(childIdx == GetHiPriChildIDX(ph,parentIdx)){   //왼쪽 노드와 비교,
        //if(lastElem.pr <= ph->heapArr[childIdx].pr) 
        if(ph->comp(lastElem,ph->heapArr[childIdx]) >= 0)   //우선순위 기준 함수의 결과값이 0보다 크거나 같으면
            break;
        ph->heapArr[parentIdx] = ph->heapArr[childIdx]; //마지막 노드보다 우선순위가 높으니, 비교대상 노드(자식 노드)의 위치정보를 한 레벨 올림
        parentIdx = childIdx;   //인덱스 변경
    }
    
    ph->heapArr[parentIdx] = lastElem;  //마지막 노드의 위치를 최종 변경
    ph->numofData -= 1;
    
    
    return retData;
    
}

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

int main(){
    Heap heap;
    HeapInit(&heap,DataPriorityComp);

    HInsert(&heap,'A');
    HInsert(&heap,'B');
    HInsert(&heap,'C');
    HInsert(&heap,'D');
    HInsert(&heap,'E');

    printf("%c \n",HDelete(&heap));
    printf("%c \n",HDelete(&heap));
    printf("%c \n",HDelete(&heap));
    printf("%c \n",HDelete(&heap));
    printf("%c \n",HDelete(&heap));
    return 0;
}