Heap

자료구조 ‘힙(heap)’

• 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)
• 힙은 일종의 반정렬 상태를 유지한다.
  • 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도
  • 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다.
• Heap은 Full Binary Tree 혹은 Complete Binary Tree에서 작동한다. 비어있는 층의 node들은 주로 NULL Pointer로 생각을 해서 구현을 한다.

Full v.s. Complete Binary Trees.   [source:https://web.cecs.pdx.edu/~sheard/course/Cs163/Doc/FullvsComplete.html]

 

• 이러한 Heap은 다른 자료구조들과 다르게 동적할당이 필요하지 않는다
  • Array로 표현이 가능하다, 메모리의 사용량이 적다.
• 아래의 사진과 같이 Heap(MaxHeap)으로 표현하면 각 계층의 관계성때문에 단순한 Array로 구현이 가능하다.

Heap의 예시

 

root node를 A[1]이라고 한다면, (1번째 node는 A[i], i-th node는 A[i])

parent node는 A[i/2], child left node는 A[i*2], child right node는 A[i*2 + 1]

위와 같이 표현이 가능하다. 

허나 root node가 A[0]이라면 규칙성은 또 다르게 작용한다. 

 

힙(heap)의 종류

• max tree
  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• min tree
  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• max heap
  • nearly complete binary tree 이면서, max tree인 Heap
  • key(부모 노드) >= key(자식 노드)

• min heap
  • nearly complete binary tree 이면서, max tree인 Heap 
  • key(부모 노드) <= key(자식 노드)

 

힙(Heap)의 구현

MaxHeapify

위와 같이 subtree의 left child, right child의 node들이 Heap을 만족하고 있을 때에 각 노드들의 root부분끼리 서로 비교를 한다면 새로운 element의 위치를 알 수 있다. 다음은 MaxHeapify를 pseudocode(알고리즘을 쉽게 이해하기 위해서 구문의 엄격한 규칙 없이 제어와 자료 구조를 설명한 것.)로 표현한 것이다.

Max-Heapify(A,i)

l=left (i)
r=right (i)
if l <= heap-size[A] and A[l]>A[i]
	then largest = l
else 
	largest = i
if r <= heap-size[A] and A[r]>A[largest] 
	then largest = r
if largest != i
	then exchange A[i] with A[largest]
		Max-Heapify(A,largest)

위와 같은 일련의 과정을 겪고 MaxHeap이 완성된다. 

 

이러한 내용을 바탕으로 MinHeap을 구현해봤다.

#include <iostream>
#include <cstring>

using namespace std ;

struct node_{
    char name[11] ; //  name consists of English alphabet (at most 10 char)
    float score ;   //  score(0.0, 100.0) is key.
} ;

typedef struct animal_{
    node_ n[31] ;   // 1 ~ 30  /  1:root / 2-left, 3-right / 
    int heapSize ;  // maxinum heap size = 30
}animal ;


void minHeapify(animal & A, int i) ; 
node_ extractMin(animal & A) ;
void heapDecreaseKey(animal & A, int i, node_ key);
void minHeapInsert(animal & A, node_ key) ;

int main(){

    bool recursive = true ;

    animal A ;
    A.heapSize = 0 ;

    char menu ;
    int index ;
    
    while(recursive){
        printf("\n*********** MENU ****************\n") ;
        printf("I : Insert new element into queue.\n") ;
        printf("D : Delete element with smallest key from queue.\n") ;
        printf("C : Decrease key of element in queue.\n") ;
        printf("P : Print out all elements in queue.\n") ;
        printf("Q : Quit\n\n") ;

        printf("Choose menu: ") ;
        scanf("%c", &menu) ;   

        node_ temp ;

        switch(menu){
            case 'I': case 'i':
                printf("Enter name of element: ") ;
                scanf("%s", temp.name) ;
                printf("Enter key value of element: ") ;
                scanf("%f", &temp.score) ;

                minHeapInsert(A, temp) ;
                printf("New element [%s, %4.1f] is inserted.\n", temp.name, temp.score) ;
                break  ;
                
            case 'D': case 'd':
                temp = extractMin(A) ;
                printf("[%s, %4.1f] is deleted.\n", temp.name, temp.score) ;
                break ;

            case 'C': case 'c':
                printf("Enter index of element: " ) ;
                scanf("%d", &index) ;
                printf("Enter new key value: ") ;
                scanf("%f", &temp.score) ;
                strcpy(temp.name, A.n[index].name) ;
                heapDecreaseKey(A, index, temp) ;
                break ;

            case 'P': case 'p':
                for(int i = 1 ; i <= A.heapSize ; i++)
                    printf("[%s, %4.1f] ", A.n[i].name, A.n[i].score) ;
                printf("\n") ;
                break ;

            case 'Q': case 'q':
                printf("Thank you. Bye!\n") ;
                recursive = false ;     // break loop ;
                break;
            default:
                break ;
        }
        getchar() ;
    }
    return 0 ;
}


void minHeapify(animal & A, int i){
    int l, r, smallest ;
    l = i * 2;
    r = i * 2 + 1 ;

    if(l <= A.heapSize && A.n[l].score < A.n[i].score)
        smallest = l ;
    else
        smallest = i ;

    if(r <= A.heapSize && A.n[r].score < A.n[smallest].score)
        smallest = r ;

    if(smallest != i){
        node_ temp = A.n[i] ;
        A.n[i] = A.n[smallest] ;
        A.n[smallest] = temp ;
        
        minHeapify(A, smallest) ;
    }
}

node_ extractMin(animal & A){
    node_ min ;
    if(A.heapSize < 1){
        printf("heap underflow") ;
        return min ;
    }

    min = A.n[1] ;

    A.n[1] = A.n[A.heapSize] ;
    A.heapSize -= 1 ;
    
    minHeapify(A, 1) ; 

    return min ;
}

void heapDecreaseKey(animal & A, int i, node_ key){
    if(key.score > A.n[i].score){
        printf("new key is smaller than current key") ;
        return ;
    }

    A.n[i] =  key ;

    while (i > 1 && A.n[i/2].score > A.n[i].score){
        node_ temp = A.n[i] ;
        A.n[i] = A.n[i/2] ;
        A.n[i/2] = temp ; 
        i = i/2 ;
    }     
}

void minHeapInsert(animal & A, node_ key){
    A.heapSize += 1 ;
    A.n[A.heapSize].score = 9999 ; //equal infinity 
    heapDecreaseKey(A, A.heapSize, key) ;
}

 

오늘 다룬 코드는 github에서도 볼 수 있습니다

github.com/gurcks8989/DataStructure/blob/master/21-1/MinHeap.cpp

gurcks8989/DataStructure