우선순위 큐의 구현 (이진 힙)

이번 포스트에서는 우선순위 큐 자료구조 구현을 위한 이진 힙에 대해서 포스트하도록 하겠습니다.

 

우선순위 큐

우선순위 큐는 큐 자료구조에서 각 노드에 우선순위를 부여하여 우선순위가 높은 순으로 삭제가 발생하는 큐를 의미합니다.

 

정렬되지 않은 배열에서 우선순위 큐를 구현한 경우, 삽입은 O(1)에 가능하나, 삭제가 O(N)의 시간복잡도가 소요됩니다.

반대로 정렬된 배열에서 우선순위 큐를 구현한 경우, 삽입은 O(N)에 가능하고 삭제는 O(1)의 시간복잡도가 소요됩니다.

 

이진 힙

이진 힙은 각 노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전이진트리 (최대힙) 이거나, 각 노드의 키 값이 자식노드의 키 값보다 작거나 같은 완전이진트리 (최소힙) 를 의미합니다.

 

이진 힙은 삽입과 삭제가 O(log n)의 시간복잡도가 소요되며, 최고 우선순위인 자료의 접근은 O(1)에 가능합니다. 따라서 우선순위 큐 구현에 용이한 자료구조라고 볼 수 있습니다.

 

최대힙의 조건으로는 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같아야합니다.

최소힙의 조건으로는 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같아야 합니다.

 

최대힙 구현

먼저 최대힙의 삽입 연산입니다.

 

최대힙의 삽입 연산은 먼저 삽입 자료를 완전이진트리의 마지막 다음 위치에 삽입하고, 삽입 노드의 키 값과 부모 노드의 키 값을 비교하여 최대힙 조건이 맞게 끔 자리를 교체합니다. 이를 반복하여 올바른 위치에 삽입 자료가 위치하게 되면 교체 작업을 중단합니다.

 

typedef struct Heap {
    int *key;        //자료가 저장될 배열
    int MAX_SIZE;    //배열의 사이즈
    int last;        //현재 배열에 마지막으로 삽입된 위치
} Heap;
 
Heap* createHeap() {            //힙 생성
    Heap* h = (Heap*)malloc(sizeof(Heap));
    h->MAX_SIZE = 2;
    h->key = (int*)malloc(sizeof(int)*2);
    h->last = -1;
    return h;
}
 
void resize(Heap* h) {
    int *key2 = (int*)malloc(sizeof(int*)(h->last + 1) * 2);                    //현재 힙 배열의 2배 크기로 새로운 힙 배열 생성
    for(int i = 0; i <= h->last; i++)    key2[i] = h->key[i];                    //기존 힙의 내용을 새로운 힙에 복사
    h->key = key2;                                                                //기존 배열을 가리키던 포인터가 새로운 힙 배열을 가리키게끔 설정
    h->MAX_SIZE = (h->last + 1) * 2;                                            //MAX_SIZE 또한 새로운 힙 배열의 최대 크기로 수정
}
 
void insert(Heap* h, int keyNew) {
    if(h->last + 1 == h->MAX_SIZE)    resize(h);                //힙이 포화상태이면 사이즈를 늘림
    int i = ++(h->last);                                    //마지막 위치에 삽입해야하므로 h->last + 1 을 i가 가짐.
    while(i > 0 && keyNew > h->key[(i-1) / 2]) {            //힙이 공백이아니고, 새로운 자료의 키 값이 부모노드의 키 값보다 크다면
        h->key[i] = h->key[(i-1) / 2];                        //위치를 교환한다.
        i = (i - 1) / 2;                                    //i도 부모노드 위치로 옮긴다.
    }
    h->key[i] = keyNew;                                        //올바른 위치를 찾았으므로 키를 삽입한다.
}

다음은 삭제 연산입니다.

 

우선순위가 제일 높은 값 (루트 노드)가 삭제 되고, 제일 마지막 노드를 루트 노드 자리로 이동합니다.

그리고, 자식 노드와 비교하면서 최대힙 조건에 맞을 때 까지 자리를 교체해줍니다.

 

int delete(Heap* h) {
    if(h->last <= 0)    exit(-1);                                            //힙이 공백일 때 삭제불가
    int keyRoot = h->key[0];                                                //root 값을 삭제해야하므로 저장
    int x = h->key[(h->last)--];                                            //마지막 노드
    int p = 0, c = 1;                                                        //부모 노드 인덱스와 자식 노드 인덱스
    for(; c <= h->last; p = c, c = 2 * p + 1) {                                //자식 노드가 마지막 위치에 도달하지 않았을 때, 반복할 때 마다 부모 노드 인덱스는 자식 노드 인덱스로, 자식 노드 인덱스는 바뀐 부모 노드의 자식 노드 인덱스를 가리킴.
        if(c < h->last && h->key[c] < h->key[c + 1]) c++;                    //자식 노드가 마지막 노드가 아니고, 오른쪽 자식 노드와 비교하여 오른쪽 자식 노드가 클 경우, c를 1 증가. (키값이 큰 노드와 비교해야 최대힙 조건만족)
        if(x >= h->key[c])    break;                                            //최대힙 조건에 만족하므로 반복문 탈출
        h->key[p] = h->key[c];                                                //부모 노드위치에 자식 노드 키값을 삽입. (자리 교체)
    }
    h->key[p] = x;                                                            //찾은 위치에 값을 삽입.
    if(h->last >= 0 && h->last + 1 <= h->MAX_SIZE / 4)    resize(h);            //힙 배열이 전체 크기의 1/4만 차지한다면 크기 리사이즈
    return keyRoot;                                                            //
}

최소힙 의 삽입, 삭제 연산은 최대힙 연산에서 조건만 반대로 설정해주면 됩니다.

 

void insert(Heap* h, int keyNew)
{
    if (h->last + 1 == h->MAX_SIZE)    resize(h);
    int i = ++(h->last);                        
    while (i > 0 && keyNew < h->key[(i - 1) / 2])                    
    {
        h->key[i] = h->key[(i - 1) / 2];                    
        i = (i - 1) / 2;                                    
    }
    h->key[i] = keyNew;
}
 
int delete(Heap* h)
{
    int keyRoot = h->key[0];            
    int x = h->key[(h->last)--];                
    int p = 0, c = 1;            
    for (; c <= h->last; p = c, c = 2 * p + 1)    
    {
        if (c < h->last && h->key[c] > h->key[c + 1])    c++;                
        if (x <= h->key[c])    break;        
        h->key[p] = h->key[c];                
    }
    h->key[p] = x;
    if (h->last >= 0 && h->last + 1 <= h->MAX_SIZE / 4)    resize(h);
    return keyRoot;
}

여기까지 우선순위 큐를 이진힙 자료구조를 통해 구현해보았습니다.

 

다음 포스트에서는 자료의 정렬에 대해서 포스트 하도록 하겠습니다.