[자료구조] 힙(Heap)이란? Max Heap, Min Heap, 힙 C언어 구현

힙(Heap)이란?

힙이란 완전이진트리의 일종으로 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다.

• 힙은 중복된 값을 허용한다.
• Max Heap 은 가장 큰 값을 빠르게 찾기 위한 것이고 Min Heap 가장 작은 값을 빠르게 찾기 위한 것이다.

완전이진트리가 무엇인지 모르겠다면 다음을 참고하자.

 

[자료구조] 트리(Tree)의 개념, 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐

 

Max Heap(최대 힙)

• Max Heap 은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다.
• 부모노드의 key >= 자식 노드의 key

Min Heap(최소 힙)

• Min Heap 은 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다.
• 부모노드의 key <= 자식 노드의 key

Heap 구현

Heap은 배열을 통해 쉽게 구현할 수 있다. 이진 탐색 트리의 경우에는 연결리스트로 구현하였는데, Heap은 배열로 구현하는 이유가 무엇일까?

그 이유는 Heap이 완전 이진 트리이기 때문이다. 완전 이진 트리의 특성상 왼쪽부터 오른쪽으로 차곡차곡 노드가 저장되므로 배열의 구조를 사용할 수 있게 된다.

아래 그림을 보면 이해가 빠를 것이다.

위 그림은 Max Heap을 배열로 표현한 것이다. 여기서 특이한 점은 0번 index를 사용하지 않는다는 것인데, 이는 구현을 쉽게 하기 위해서이다. index를 통해 노드를 접근할 수 있는데, 이를 다음과 같이 정리 할 수 있다.

• 부모노드의 index = (자식노드의 index) / 2     (ex : index 4번 노드의 부모노드 : index 2번 노드)
• 왼쪽 자식 노드의 index = (부모노드의 index)*2     (ex : index 3번 노드의 왼쪽 자식 노드 : index 6번 노드)
• 오른쪽 자식 노드의 index = (부모노드의 index)*2 + 1   (ex : index 3번 노드의 오른쪽 자식 노드 : index 7번노드)

 

타입 정의 소스코드

#include <stdio.h>
#define MAX_SIZE 100    // Heap 의 최대 원소 개수 

typedef struct{    // Heap 의  노드 
    int key;    // Heap 의 key
    /* 여기에 데이터 추가 가능 ex) int data */ 
}element;    

typedef struct{    // Heap 자료구조 
    element heap[MAX_SIZE];     
    int size;
};

Heap 의 삽입

힙의 삽입은 다음과 같은 과정을 거친다.

1. 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다. ( = 배열의 마지막에 원소를 추가한다. )
2. 새로운 노드를 부모 노드와 비교해서 교환해야 한다면 힙의 성질을 만족 할 때까지 교환한다.

예를 들어 위의 Max Heap에 새로운 노드(key=8)를 추가한다고 하자.

첫 번째로 배열의 가장 마지막 위치에 새로운 원소 8을 추가한다.

두 번째로 부모노드인 index 4번 노드와 키 값을 비교한다. 이 때 자식노드인 index 8번 노드가 키 값이 더 크므로(8>4) 부모노드와 위치를 교환한다.

 

마지막으로 부모노드인 index 2번 노드와 키 값을 비교한다. 이 때 자식노드인 index 4번 노드가 키 값이 더 크므로(8>7) 부모노드와 위치를 교환한다. 이렇게 하면 Max Heap 의 성질을 만족하게 되고 삽입 과정이 종료된다.

Max Heap 을 예로 들었다. Min Heap 은 반대로 부모노드가 자식노드보다 작도록 교환하면 된다. 

Heap의 삽입 소스코드

void max_heap_insert(Heap* h, element item){
    int i;
    i = ++(h->size);    // 마지막 위치(마지막 원소의 index+1) 
    
    /* 루트노드가 아니고, 삽입할 값이 적절한 위치를 찾을 때까지*/
    while( (i != 1) && (item.key > h->heap[i/2].key) ){
        h->heap[i] = h->heap[i/2];    // 자식 노드와 부모노드 교환 
        i /= 2;    // 한 레벨 위로 올라감 
    }
    
    h->heap[i] = item;    // 새로운 노드 삽입     
}

Heap 의 삭제

Heap 에서의 삭제는 루트 노드를 삭제하고 반환한다는 뜻이다.

- Max Heap 에서의 삭제는 가장 큰 키 값을 가진 노드(root node)를 삭제하고 반환한다는 뜻이다.

- Min Heap 에서의 삭제는 가장 작은 키 값을 가진 노드(root node)를 삭제하고 반환한다는 뜻이다.

따라서 Heap에서의 삭제는 다음과 같은 과정을 거친다

1. 루트노드를 삭제한다. ( 나중에 값을 반환해야 하므로 따로 저장해놓는다)
2. 삭제된 루트 노드의 위치에 힙의 가장 마지막 노드를 가져온다.
3. 힙의 조건에 맞게 위치를 재설정한다. ( 이것을 heapify 라고 한다 )

그림을 보며 이해해보자. 여기서는 Max Heap 을 예시로 한다.

1. 루트노드를 삭제한다. ( 나중에 값을 반환해야 하므로 따로 저장해놓는다)

2. 삭제된 루트 노드의 위치에 힙의 가장 마지막 노드를 가져온다.

3. 힙의 조건에 맞게 위치를 재설정한다. (heapify)

이때 주의 할 점은 비교할 노드보다 큰 자식 노드가 2개 있을 때, 더 큰 값을 가진 자식 노드와 교환해야 한다는 것이다.

따라서 위에서는 index 1번 노드와 index 2번 노드가 교환되게 된다. ( 8>6 )

이후 힙의 조건에 맞게 위치를 재설정하면 된다. 위와 같은 과정을 거치면 삭제가 완료된다.

Max Heap 의 조건을 만족하는 것을 확인 할 수 있다.

Heap의 삭제 소스코드

element max_heap_delete(Heap* h){
    int parent, child;
    element item, temp;
    
    item = h->heap[1];    // 반환할 노드 저장
    temp = h->heap[(h->size)--];    // 마지막 노드 temp 에 저장, 사이즈 1감소
    parent = 1;     
    child = 2; 
    
    while(child <= h->size){
        /* 왼쪽 자식 노드와 오른쪽 자식 노드 중 더 큰 자식 노드*/
        if( (child < h->size) && ((h->heap[child].key) < h->heap[child+1].key )){
            child++;    // 오른쪽 자식 노드 선택
        }
        
        /* 마지막 노드가 자식 노드보다 크면 종료 */
        if(temp.key >= h->heap[child].key){
            break;
        } 
        
        /* 부모노드와 자식노드 교환 */
        h->heap[parent] = h->heap[child];
        
        /* 한 레벨 아래로 이동 */ 
        parent = child;
        child *= 2;
    }
    
    /* 마지막 노드를 재설정한 위치에 삽입 */ 
    h->heap[parent] = temp;
    
    /* 최댓값 노드 반환 */ 
    return item;    
    
} 

전체 소스코드

#include <stdio.h>
#define MAX_SIZE 100    // Heap 의 최대 원소 개수 

typedef struct{    // Heap 의  노드 
    int key;    // Heap 의 key
    /* 여기에 데이터 추가 가능 ex) int data */ 
}element;    

typedef struct{    // Heap 자료구조 
    element heap[MAX_SIZE];     
    int size;
}Heap;


void max_heap_insert(Heap* h, element item){
    int i;
    i = ++(h->size);    // 마지막 위치(마지막 원소의 index+1) 
    
    /* 루트노드가 아니고, 삽입할 값이 적절한 위치를 찾을 때까지*/
    while( (i != 1) && (item.key > h->heap[i/2].key) ){
        h->heap[i] = h->heap[i/2];    // 자식 노드와 부모노드 교환 
        i /= 2;    // 한 레벨 위로 올라감 
    }
    
    h->heap[i] = item;    // 새로운 노드 삽입     
}

element max_heap_delete(Heap* h){
    int parent, child;
    element item, temp;
    
    item = h->heap[1];    // 반환할 노드 저장
    temp = h->heap[(h->size)--];    // 마지막 노드 temp 에 저장, 사이즈 1감소
    parent = 1;     
    child = 2; 
    
    while(child <= h->size){
        /* 왼쪽 자식 노드와 오른쪽 자식 노드 중 더 큰 자식 노드*/
        if( (child < h->size) && ((h->heap[child].key) < h->heap[child+1].key )){
            child++;    // 오른쪽 자식 노드 선택
        }
        
        /* 마지막 노드가 자식 노드보다 크면 종료 */
        if(temp.key >= h->heap[child].key){
            break;
        } 
        
        /* 부모노드와 자식노드 교환 */
        h->heap[parent] = h->heap[child];
        
        /* 한 레벨 아래로 이동 */ 
        parent = child;
        child *= 2;
    }
    
    /* 마지막 노드를 재설정한 위치에 삽입 */ 
    h->heap[parent] = temp;
    
    /* 최댓값 노드 반환 */ 
    return item;    
    
} 


int main(){
    Heap max_heap;
    element item;
    item.key = 9;
    max_heap_insert(&max_heap, item);
    item.key = 7;
    max_heap_insert(&max_heap, item);
    item.key = 6;
    max_heap_insert(&max_heap, item);
    item.key = 4;
    max_heap_insert(&max_heap, item);
    item.key = 5;
    max_heap_insert(&max_heap, item);
    item.key = 1;
    max_heap_insert(&max_heap, item);
    item.key = 3;
    max_heap_insert(&max_heap, item);
    item.key = 8;
    max_heap_insert(&max_heap, item);
    
    while(max_heap.size > 0){
        item = max_heap_delete(&max_heap);
        printf("%d ", item.key);
    }
        
    return 0;
}

 

실행결과