[C] 힙과 우선순위 큐

힙(Heap)과 우선순위 큐(Priority Queue)에 대해 알아보자.

 

1. 힙 (Heap)

여기서 배우는 힙은 메모리상의 힙이 아니다!!! 자료구조의 첫장 <메모리의 구조> 안에 코드, 데이터, 스택, 힙 영역이 있다는 건 배웠을 것이다. 하지만 이 힙은 힙 정렬을 배우기 위한 자료구조 구현 방법이다. 밑에 우선순위 큐를 구현하기 위해 힙을 이용한다.

 

힙이란 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 예를 들어, 가장 큰 값을 빠르게 찾기 위해선 다음과 같은 최대 힙 트리를 만드는 게 좋다.

 

출처 : http://www.equestionanswers.com/c/c-heap-sort.php

 

잘 보면 우리가 지금까지 배워오던 이진트리와는 아주 다르다. 이진트리는 루트노드를 기준으로 작은 값은 왼쪽 서브트리에, 큰 값은 오른쪽 서브트리에 배정된 형태이다. 최대 힙 트리는 루트노드의 키 값이 자손노드들의 키 값보다 항상 크거나 같다.

key(부모노드) ≥ key(자식노드) 

또, 힙 트리에서는 중복 키값을 허용한다. BST에서는 중복 키값을 허용하지 않았다.

그리고 힙 트리는 완전이진트리(complete binary tree)의 형태를 가진다. 완전이진트리가 무엇인지는 [C]트리와 이진트리 포스트에서 설명했다. 위의 그림은 레벨 4의 단말노드가 왼쪽부터 채워졌으니 완전이진트리의 성질을 만족하므로, 힙 트리가 맞다.

 

힙 트리가 완전이진트리임을 감안하면 높이 h가 log(n)이 된다는 걸 알 수 있다. 즉, 삭제와 삽입의 시간 복잡도는 둘 다 O(log(n)). AVL트리와 같은데, 아마 둘 다 '균형잡힌 트리'이기 때문인 듯...

 

 

 

2. 우선순위 큐 (Priority Queue)

우선순위 큐는 우선 순위의 개념을 큐에 도입한 자료구조이다. 알다싶이 큐는 FIFO의 원칙을 따르기 때문에 먼저 들어간 데이터가 먼저 나간다. 하지만 우선순위 큐는 데이터들이 우선 순위(가중치)를 가지고 있기 때문에, 먼저 들어온 순서대로 나가는 것이 아니라 우선 순위에 따라서 나가게 된다. 예를 들어, 최대 힙 같은 경우 가장 가중치가 큰 데이터가 먼저 나간다.

 

• 응용 분야: 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영 체제에서의 작업 스케쥴, 수치 해석적 계산

우선순위 큐는 배열, 연결리스트 등의 여러가지 방법으로 구현이 가능하다. 여기서는 위에서 배운 힙 구조를 통해 구현해볼 것이다. 

 

 

우선순위 큐의 구현

힙 트리에서 삽입연산을 하기 위해서는 부모노드의 인덱스와 자식노드의 인덱스 간 관계를 알아야 한다.

참고로 인덱스는 루트노드가 1, 가장 나중에 들어온 노드가 n인 순이다(0은 비운다는 뜻).

 

출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

• 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
• 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
• 부모의 인덱스 = (자식의 인덱스)/2

일단 새로 삽입하는 노드를 말단에 위치시키고 부모노드와 계속 비교하면서 올려야할지 올리지 말아야 할지 결정한다.

 

삭제연산은 반대로 새로 삽입하는 노드를 루트노드에 위치시키기 위해 루트노드를 삭제한다(!). 가장 위에서부터 자식노드들과의 비교를 통해 내릴지 말지 결정하는 과정이다. 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define MAX_SIZE 20
 
typedef struct {
    int key;
}element;
 
typedef struct HypeNode {
    element heap[MAX_SIZE];
    int heap_size;
}Node;
 
void upheap(Node* h, element item) { //현재 요소의 개수가 heap_size개인 힙 h에 item을 삽입한다.
    int i;
 
    i = ++(h->heap_size);
 
    while ((i != 1) && (item.key > h->heap[i / 2].key)) {
        h->heap[i] = h->heap[i / 2];
        i /= 2; //부모노드의 인덱스 = (자식노드의 인덱스)/2임을 기억하자. 계속해서 트리를 거슬러 올라가는 중!
    }
    h->heap[i] = item;
}
element downheap(Node* h) {
    int parent, child;
    element item, temp;
 
    item = h->heap[1]; //루트노드를 반환하기 위해 item에 루트노드 값 저장
    temp = h->heap[h->heap_size]; //새로 넣는 노드(마지막 노드)를 temp에 할당
    h->heap_size -= 1; //힙 크기 하나 줄임
    parent = 1;
    child = 2;
    /*
    자... 왜 parent가 1이고 child가 2일까를 고민해봤다.
    아마 왼쪽자식부터 비교한다는 얘기인 것 같다.
    힙트리도 이진트리이기 때문에, 루트노드의 인덱스가 1이면 왼쪽 자식노드들은 모두 짝수의 값을 갖게 된다(0이거나 짝수)
    */
    while (child <= h->heap_size) {
        if ((child < h->heap_size) && (h->heap[child].key < h->heap[child + 1].key)) //현재 노드의 자식노드 중 더 큰 값 찾기
            child++;
        if (temp.key >= h->heap[child].key) // 새로 넣는 노드가 더 큰 자식의 값보다 크다면 while문 탈출
            break;
        h->heap[parent] = h->heap[child];
        parent = child;
        child *= 2;
    }
    //temp는 새로 들어온 노드이다. 그것을 재구성한 위치에 넣음
    h->heap[parent] = temp;
    return item; //최대값 반환
}

 

삽입과 삭제연산만 구현해보았는데, 아래의 함수들도 포함시켜 최대 힙의 전체 프로그램을 짜봤다.

 

• init(): 힙 트리를 초기화한다.
• upheap(item): item값을 가진 새로운 노드를 삽입한다.
• downheap(): 최대값을 가진 요소를 삭제한다. (user input으로 지정해주는 값을 삭제하는 것이 아님을 주의!!)
• print_all(): 힙 트리를 출력한다.

 

 문제는 저 print_all()함수이다. 트리 모양대로

9

8 7

3 5 3 4

2

이렇게 출력하고 싶었는데 어떤식으로 print 함수를 짜야할지 모르겠다(...) 일단 미완성 코드지만 백업해둔다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define MAX_SIZE 20
 
typedef struct {
    int key;
}element;
 
typedef struct HypeNode {
    element heap[MAX_SIZE];
    int heap_size;
}Node;
 
void init(Node* h) {
    h->heap_size = 0;
}
void upheap(Node* h, element item) {
    int i;
 
    i = ++(h->heap_size);
 
    while ((i != 1) && (item.key > h->heap[i / 2].key)) {
        h->heap[i] = h->heap[i / 2];
        i /= 2;
    }
    h->heap[i] = item;
}
element downheap(Node* h) {
    int parent, child;
    element item, temp;
 
    item = h->heap[1]; 
    temp = h->heap[h->heap_size];
    h->heap_size -= 1;
    parent = 1;
    child = 2;
    
    while (child <= h->heap_size) {
        if ((child < h->heap_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;
}
void print_all(Node* h) {
    
    /* ????? */
 
    }
}
 
int main(void) {
    Node heap;
 
    element e1 = { 2 }, e2 = { 5 }, e3 = { 4 }, e4 = { 8 }, e5 = { 9 }, e6 = { 3 }, e7 = { 7 }, e8 = { 3 };
 
    init(&heap);
    upheap(&heap, e1);
    upheap(&heap, e2);
    upheap(&heap, e3);
    upheap(&heap, e4);
    upheap(&heap, e5);
    upheap(&heap, e6);
    upheap(&heap, e7);
    upheap(&heap, e8);
    print_all(&heap);
 
    downheap(&heap);
    print_all(&heap);
    downheap(&heap);
    print_all(&heap);
    printf("\n");
 
    return 0;
}

 

나머지 자료를 백업하는데로 와서 고쳐봐야지~~