Heap

Heap

    - 영어로는 '쌓아올리다.' 의미

    - 형태 : 완전 이진 트리

    - 원리 : 요소들 중에 최대값/최소값을 가져오기 고안된 트리형 자료구조

 

 

 

종류

    - 최대 힙

        * 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

        * 부모 노드 key value >= 자식 노드 key value

 

    - 최소 힙

        * 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

        * 부모 노드 key value <= 자식 노드 key value

 

 

 

특징

    - 중복 키 값 허용

    - 완전 이진 이진 트리 구조를 가진 이유는 최적화 때문이다. 단순히 최댓값/최솟값만 O(1)안에 찾기 위해서라면 다른 배열이나 리스트도 가능하다. 그러나, 삽입/삭제에서 stable하기 위해서 완전 이진 트리를 사용한다.

    - 삽입/삭제 시간 복잡도 : O(logN)

 

 

 

구현 (최소 힙)

    - 특징

        * 힙을 저장하는 표준 자료구조는 배열

        * 구현을 쉽게 하기 위해서 첫 번째 index는 0이 아닌 1을 사용

        * 부모 노드와 자식 노드의 관계

            + 왼쪽 자식 index = 부모 노드 index * 2

            + 오른쪽 자식 index = 부모 노드 index * 2 + 1

            + 부모 노드 index = 자식 노드 index / 2

 

 

    - 삽입

        1. 가장 끝 노드에 새로운 요소 삽입

        2. 삽입된 노드와 부모를 비교

        3. 부모 노드와 비교하여 자식 노드가 더 작은 값이면 부모와 교환, 그렇지 않으면 그대로

        4. 조건(최소 힙 구조)를 만족할 때까지 3번 반복

 

// 최소 힙 삽입 함수
void insert_min_heap(int heap[], int element, int heap_size) {
    
    // 현재 삽입할 위치
    // 삽입하므로 크기 늘리기
    int i = ++heap_size;
    
    // 삽입할 위치가 root 노드는 아니고 + 부모보다 작으면 부모와 위치 교환
    // i = 1이면, 1/2 = 0이 되어 버림. index=0은 사용하지 않음
    while((i != 1) && (element < heap[i/2]) ){
        heap[i] = heap[i/2];
        i /= 2;
    }
    
    // 더 이상 교환 하지 않아도 됨
    // 현재 위치에 element 삽입
    heap[i] = element;
}
 

 

 

  - 삭제

        1. root 노드 제거

        2. root 노드 자리에 가장 마지막 노드 삽입

        3. root 노드와 자식 노드 비교

        4. 부모 노드와 비교하여 자식 노드가 더 작은 값이면 교환, 그렇지 않으면 그대로

            4-1. 부모보다 더 작은 자식이 없으면 종료

            4-2. 부모보다 더 작은 자식이 하나 있으면 교환

            4-3. 부모보다 더 작은 자식이 두 개 있으면, 더 작은 자식과 교환

        5. 조건(최소 힙 구조)을 만족할 때까지 4번 반복

 

 

 

// 최소 힙(min heap) 삭제 함수
int delete_min_heap(int heap[], int heap_size) {
 
    int p, c, min_num, tmp;
 
    min_num = heap[1]; // 최소값 저장
    tmp = heap[heap_size--]; // 마지막 노드 값 임시 저장
 
    p = 1; // 초반에 index = 1을 root 노드로 하기로 했었습니다.
    c = 2;
 
    // heap_size보다 작거나 같을 때까지
    while (heap_size >= c) {
 
        // 두 개의 자식 중 더 작은 자식 선택
        // 현재 child은 왼쪽 자식을 가리킴으로 child < heap_size가 되어야 오른쪽 자식 포함
        if(c < heap_size && (heap[c] > heap[c+1]))
            c++;
 
        // 비교할 자식 선택 완료
        // 현재 p(부모) 위치에 있는 tmp와 c(자식) 노드를 비교해서 tmp가 더 작으면 교환 필요 없음
        // 처음에는 p의 노드가 root 노드
        if(tmp < heap[c]) break;
 
        // 교환 필요함
        heap[p] = heap[c];
        p = c;
        c *= 2;
    }
    
    // 최종적으로 p 위치에 tmp 
    heap[p] = tmp;
 
    return min_num;
}
 

 

 

 

사용

    - 우선순위 큐 구현

    - 무손실 압축 알고리즘인 허프만 코드 구현

 

 

 

참조

    - 블로그 1

    - 위키피디아

    - 나무위키