힙(Heap)

이번 포스트에서는 자료구조의 힙(Heap)에 대해 다루도록 하겠습니다.

힙이란?

: 완전 이진 트리 구조의 일종으로 우선순위 큐를 위해 만들어진 자료구조입니다.

 

힙의 종류 : 

• 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 (부모 key ≥ 자식 key)

최대 힙

• 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 (부모 key ≤ 자식 key)

최소 힙

최대 힙(Max Heap)의 추가 및 삭제 :

최대 힙 추가 소스 코드 : 

void push_max_heap(element item, int *n)
{
    int i;
    if (HEAP_FULL(*n)) {
    	fprintf(stderr, "The heap is full.\n");
        exit(1);
    }
    i = ++(*n);
    while ((i != 1) && (item.key > heap[i / 2].key)) {
    	heap[i] = heap[i / 2];
        i /= 2;
    }
    heap[i] = item;
}

소스 코드 분석 : 

먼저 만원 힙인지를 검사합니다. 힙이 만원이 아니면 변수 i를 새로운 힙 크기인 n(노드의 수) + 1로 설정합니다. 그 다음 힙에서 삽입된 항목의 올바른 위치를 결정합니다. i 값이 1이 아니면서 삽입한 가지의 값이 부모의 값보다 클 동안에 while 루프를 사용합니다. while 문이 도는 동안에 부모의 값을 아래로 이동시킨 다음에 레벨을 올립니다. 힙은 n개의 원소를 갖는 완전 이진 트리이므로 높이는 [log2(n+1)]입니다. 이것은 while문이 O(log2n)만큼 반복됨을 의미합니다.

 

최대 힙 삭제 소스 코드 :

element pop_max_heap(int *n)
{
    int parent, child;
    element item, temp;
    
    if (HEAP_EMPTY(*n)) {
    	fprintf(stderr, "The heap is empty.\n");
        exit(1);
    }
    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;
}

소스 코드 분석 : 

먼저 힙이 비어있는지를 확인합니다. 비어있지 않으면 제일 마지막 노드를 비교 대상으로 정하여 루트 노드부터 시작해서 힙이 재구성될 때까지 힙의 아래 방향으로 이동합니다. while 루프를 통해 비교 대상보다 큰 자식 노드가 없을 때까지 두개의 자식 노드 중 더 큰 쪽과 비교하면서 위치를 바꿉니다. n개의 원소를 가진 힙의 높이는 [log2(n+1)]이므로 while문은 O(log2n)번 반복됩니다.

 

최소 힙(Min Heap)의 추가 및 삭제 :

최소 힙 추가 소스 코드 :

void push_min_heap(element item, int *n)
{
    int i;
    if (HEAP_FULL(*n)) {
    	fprintf(stderr, "The heap is full.\n");
        exit(1);
    }
    i = ++(*n);
    while ((i != 1) && (item < heap[i / 2])) {
    	heap[i] = heap[i / 2];
        i /= 2; 
    }
    heap[i] = item;
}

소스 코드 분석 : 

먼저 만원 힙인지를 검사합니다. 힙이 만원이 아니면 변수 i를 새로운 힙 크기인 n(노드의 수) + 1로 설정합니다. 그 다음 힙에서 삽입된 항목의 올바른 위치를 결정합니다. i 값이 1이 아니면서 삽입한 가지의 값이 부모의 값보다 작을 동안에 while 루프를 사용합니다. while 문이 도는 동안에 부모의 값을 아래로 이동시킨 다음에 레벨을 올립니다. 힙은 n개의 원소를 갖는 완전 이진 트리이므로 높이는 [log2(n+1)]입니다. 이것은 while문이 O(log2n)만큼 반복됨을 의미합니다.

 

최소 힙 삭제 소스 코드 :

element pop_min_heap(int *n)
{
    int parent, child;
    char item, temp;
    
    if (HEAP_EMPTY(*n)) {
    	fprintf(stderr, "The heap is empty.\n");
        exit(1);
    }
    item = heap[1];
    temp = heap[(*n)--];
    parent = 1;
    child = 2;
    while (child <= *n) {
    	if ((child < *n) && (heap[child] > heap[child + 1]))
        	child++;
        if (temp <= heap[child])
        	break;
        heap[parent] = heap[child];
       	parent = child;
        child *= 2;
    }
    heap[parent] = temp;
    return item
}

소스 코드 분석 : 

먼저 힙이 비어있는지를 확인합니다. 비어있지 않으면 제일 마지막 노드를 비교 대상으로 정하여 루트 노드부터 시작해서 힙이 재구성될 때까지 힙의 아래 방향으로 이동합니다. while 루프를 통해 비교 대상보다 작은 자식 노드가 없을 때까지 두개의 자식 노드 중 더 작은 쪽과 비교하면서 위치를 바꿉니다. n개의 원소를 가진 힙의 높이는 [log2(n+1)]이므로 while문은 O(log2n)번 반복됩니다.