[자료구조]우선순위 큐의 이해

우선순위 큐는 앞에서 배운 큐와 비슷하지만 다른 점이 있다.

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

 

우선순위는 프로그래머가 목적에 맞게 결정하면 된다.

그래서 우선순위 정보는 정수로 저장되어야 한다.

 

배열로 큐를 만들어 저장할 경우, 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치 시킨다. 이렇게 하면 우선순위가 높은 데이터를 반환 및 소멸이 어렵지 않다.

단점은 데이터를 삽입 및 삭제하는 과정에서 데이터를 앞뒤로 밀거나 당기거나 해야한다. 또한 우선순위에 맞는 위치를 찾기 위해 모든 데이터와 우선순위 비교 연산을 해야 한다는 점이다.

 

연결 리스트의 경우도 비슷하게 우선순위에 맞는 위치를 찾기 위해 모든 데이터와 우선순위 비교 연산을 해야한다.

 

그래서 힙이라는 방식을 이용해 저장한다.

힙은 완전 이진 트리이다. 그리고 루트 노드의 우선 순위가 제일 높아야 한다.

 

최대 힙은 상위 레벨로 갈수록 저장되는 데이터 값이 커지는 트리이다.

 

 

최소 힙은 레벨이 낮아질수록 저장되는 데이터 값이 작아지는 트리이다.

 

 

힙에서의 데이터 저장과정

트리에 새로운 데이터를 저장하는 방법은

1.우선순위가 가장 낮다는 가정하에 마지막 위치에 저장.

2.부모 노드와 우선순위를 비교해 위치를 바꾼다.

3.다시 부모 노드와 우선순위 비교.

 

 

힙에서의 데이터 삭제과정

데이터를 삭제할 때도 우선순위에 따라 데이터를 삭제해야 한다.

하지만 루트 노드를 삭제하게 되면 자식 노드들이 모양을 유지할 수 없다. 어떻게 해야 할까?

마지막 레벨의 가장 오른쪽에 위치한 노드를 가져다 루트 노드에 위치시킨 후 자식 노드와의 비교를 통해 제자리를 찾아가게 한다.

 

 

책에서 힙의 구현을 배열기반으로 했다. 연결 리스트를 기반으로 힙을 구현하면, 새료운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않기 때문이다.

 

배열기반 구현을 위해 필요한건 각 노드들의 인덱스를 알아내는 방법이다. 일단 0번째 인덱스는 사용하지 않는다.

 

 

위 사진으로 인덱스를 계산해보자.

값1의 인덱스를 1이라고 하면 4의 인덱스는 2, 2의 인덱스는 3이다.

7은 4,

5는 5,

3은 6,

다음 3은 7,

7은 8,

8은 9,

9는 10

 

부모 노드를 기준으로

왼쪽 자식 노드의 인덱스 값은 부모 노드의 인덱스*2 

오른쪽 자식 노드의 인덱스 값은 부모 노드의 인덱스*2+1

부모 노드의 인덱스 값은 자식 노드의 인덱스 값/2 

 

#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];  //HeapElem 구조체 타입으로 선언해 pr과 data를 동시에 가질 수 있음
}Heap;

void HeapInit(Heap * ph){
    ph->numofData = 0;
}

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->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;   
    printf("%d 번째,%c 추가됨\n",pr,data);
}

HData HDelete(Heap * ph){
    HData retData = (ph->heapArr[1]).data;  //부모 노드
    HeapElem 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) //가장 마지막 노드와 루트 노드 다음으로 우선순위 높은 노드 비교했을 때 마지막 노드의 우선순위가 높다면 
            break;
        ph->heapArr[parentIdx] = ph->heapArr[childIdx]; //마지막 노드보다 우선순위가 높으니, 비교대상 노드(자식 노드)의 위치정보를 한 레벨 올림
        parentIdx = childIdx;   //인덱스 변경
    }
    
    ph->heapArr[parentIdx] = lastElem;  //마지막 노드의 위치를 최종 변경
    ph->numofData -= 1;
    
    return retData;

}

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

    HInsert(&heap,'A',4);
    HInsert(&heap,'B',3);
    HInsert(&heap,'C',2);
    HInsert(&heap,'D',1);
    HInsert(&heap,'E',5);

    printf("1: %c \n",HDelete(&heap));
    printf("2: %c \n",HDelete(&heap));
    printf("3: %c \n",HDelete(&heap));
    printf("4: %c \n",HDelete(&heap));
    printf("5: %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));
}