[자료구조]힙(Heap) - 최대 힙(Max Heap), 최소 힙(Min Heap)

힙(Heap)

-힙(Heap)이란, 부모 노드와 자식 노드 간에 대소 관계가 성립하는 완전 이진 트리 기반의 자료구조 입니다.

 

최대 힙(Max Heap)과 최소 힙(Min Heap)

-최대 힙(Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙

-최소 힙(Min Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙

 

Heap 코드

배열 방식으로 힙을 구현해보겠습니다.(C언어)

 

힙을 구현하기 위해서는, 먼저 아래와 같은 코드가 필요합니다.

 

#define HEAP_SIZE 100;

typedef struct element {
    int key;
} element;

element heap[HEAP_SIZE];
int n = 0;

 

다음은 힙에 요소를 추가하는 코드입니다.

 

void push(element item) {
    int i;
    i = ++n;
    while((i != 1) && (item.key > heap[i/2].key))
    {
        heap[i] = heap[i/2];
        i /= 2;
    }
    heap[i] = item;
}

 

위 코드는 다음과 같은 방식으로 실행됩니다.

1. n은 heap에 담긴 노드의 개수입니다. i를 추가하는 노드를 포함한 전체 노드의 개수로 초기화 합니다. i는 추가하고자 하는 노드(item)의 현재 인덱스 입니다. 즉, 처음에는 item이 가장 낮은 레벨에 있습니다.
2. while문을 통해 item의 key 값을 item의 부모 노드의 key 값과 비교합니다. 만약 item의 key 값이 더 크면 item을 item의 부모 노드와 바꾸고 i(item의 현재 인덱스)를 해당 위치로 수정합니다. item의 key 값이 item의 부모 노드의 key 값보다 작거나 같은 때까지 반복합니다.  ------ (만약 heap이 원래 비어있었다면 i=1 입니다. 반복문을 실행할 필요 없이 인덱스 i에 item을 넣어주면 됩니다.)
3. while문이 종료되면 heap에서 인덱스 i에 item을 넣습니다. 

 

 

 

 

다음은 힙에서 root 노드를 빼오는 코드입니다. 

 

 

element pop(){
    int parent, child;
    element item, temp;
    item = heap[1];
    temp = heap[n--];
    parent = 1;
    child = 2;
    while(child <= n)
    {
        if(child < n) && (heap[child].key < heap[child+1].key)
        {
            child++;
        }
        if(temp.key >= heap[child].key)
        {
            break;
        }
        heap[parent] = heap[child];
        parent = child;
        child *= 2;
    }
    heap[parent] = temp;
    return item;
}

위 코드는 다음과 같은 방식으로 실행됩니다.

1. 빼고자 하는 노드(heap[1])를 item에 넣습니다.
2. parent를 1, child를 2로 초기화 합니다.
3. n은 원래 heap에 있던 노드의 개수입니다. while문은 child가 n보다 작거나 같은 동안 실행됩니다.
4. 첫 번째 if문을 통해 두 자식 노드 중 key 값이 더 큰 노드의 인덱스를 child에 저장합니다. 만약 왼쪽 자식 노드가 더 크면 child는 그대로이면 됩니다. 하지만 오른쪽 자식 노드가 더 크면 child에 1을 더해주어야 합니다.
5. 두 번째 if문은, temp의 key 값이 인덱스 child에 있는 노드의 key 값보다 크거나 같은 경우 while문을 종료합니다. heap은 완전이진트리 입니다. 따라서 이 조건을 만족시키는 방식으로 수정이 이루어져 합니다. if문의 조건을 만족시킨다는 것은, temp가 해당 자식 노드의 부모 노드가 될 자격이 있다는 뜻입니다. 따라서  이 경우에는 while문이 종료되고 인덱스 parent에 temp를 넣으면 됩니다.
6. 만약 두 번째 if문에서 종료되는 않는다면, 인덱스 child에 있던 노드를 인덱스 parent로 옮기고 parent는 child, child는 child/2로 초기화 하고 계속 while문은 반복합니다.
7. 만약 두 번째 if문이 실행되지 않고 while문이 종료된다면, 완전이진트리 형식을 유지하기 위해 인덱스 parent에는 temp가 저장되어야 합니다. 해당 인덱스의 노드는 리프 노드이기 때문에 자식 노드의 key 값을 고려할 필요가 없겠죠? 자식 노드가 없으니까요.
8. 이렇게 heap이 수정된 후, item을 반환합니다.