[자료구조] - 우선순위 큐와 히프 (Priority Queue, Heap)

---

---

우선순위 큐의 정의

우선순위 큐는 "우선 순위" 개념을 큐에 적용한 자료구조입니다. 일반적인 큐는 선입선출의 원리에 따라 "가장 먼저 들어온 데이터가 가장 먼저 나가게 됩니다." 우선순위 큐는 일반적인 큐와 달리, 데이터들이 각각 우선 순위를 가지고 우선 순위가 높은 큐가 가장 먼저 나가게 됩니다. 이러한 우선순위 큐는 여러 방법으로 구현할 수 있는데, 배열, 연결 리스트, 히프 등을 사용하여 구현할 수 있습니다.

그 중, "히프"는 완전 이진 트리로서 우선순위 큐를 구현할 때 가장 많이 사용되는 자료구조입니다.

---

히프의 정의

히프는 우선순위 큐를 구현하기 위한 자료구조로서, 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내기 위해 만들어진 자료구조입니다. 다음과 같은 트리가 바로 히프입니다. 중복 값을 허용하지 않는 완전 이진 트리입니다.

출처: https://api.ahribori.com/image/9IM1JNmiHeZRTxdgKK1VUO5C.png

히프에는 두 가지 종류의 히프트리가 존재합니다. 부모 노드의 키 값이 자식 노드보다 큰 "최대 히프", 부모 노드의 키 값이 자식 노드보다 작은 "최소 히프"입니다. 이 두 가지의 히프는 부등호의 방향만 다를 뿐, 나머지 개념은 동일합니다.

• 최대 히프: $ key$ (부모노드) $\geq$ $key$ (자식노드), 부모 노드의 키 값이 자식 노드보다 큰 히프
• 최소 히프:  $ key$ (부모노드) $\leq$ $key$ (자식노드), 부모 노드의 키 값이 자식 노드보다 작은 히프

---

히프의 삽입과 삭제

히프의 삽입과 삭제 연산에 대해서 알아보도록 하겠습니다. 이 포스팅에서 다루는 히프의 삽입과 삭제 연산은 최대 히프를 예시로 들어 설명을 진행합니다.

삽입 연산

삽입 연산을 진행하면 다음과 같은 과정을 거치게 됩니다.

1. 먼저 번호순으로 가장 마지막 위치에 이어 새로운 요소가 삽입된다.
2. 부모 노드와 비교하여 삽입된 노드가 더 크면 교환한다.
3. 과정 2를 계속 반복하여 교환한다. 그리고 삽입된 요소가 부모 요소보다 더 작다면 교환을 중단한다.

이 과정을 그림으로 나타내면 다음과 같습니다.

삭제 연산

삭제 연산을 진행하면 다음과 같은 과정을 거치게 됩니다.

1. 최대 히프에서 최대값은 루트 노드이기에 루트 노드가 삭제되고,
2. 빈 루트 노드 자리는 히프의 마지막 노드가 차지한다.
3. 새로운 루트 노드와 자식 노드를 비교하며 자식 노드가 더 클 경우, 루트 노드와 교환을 진행한다.
4. 과정 3을 계속 반복하며 진행하고, 자식 노드보다 루트 노드가 더 클 경우 교환을 중단한다.

이 과정을 그림으로 나타내면 다음과 같습니다.

---

히프 구현

히프를 C언어로 구현하면 다음과 같습니다.

#include <stdio.h>
#include <stdlib.h>
#define MAX_ELEMENT 200

typedef struct {
    int key;
} element;
typedef struct {
    element heap[MAX_ELEMENT];
    int heap_size;
} HeapType;

// 생성 함수
HeapType* create() {
    return (HeapType *)malloc(sizeof(HeapType));
}

// 초기화 함수
void init(HeapType* h) {
    h->heap_size = 0;
}

// 현재 요소의 개수가 heap_size인 히프 h에 item을 삽입한다.
// 삽입 함수 
void insert_max_heap(HeapType* 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 = i / 2;
    }
    h->heap[i] = item; // 새로운 노드 삽입
}

// 삭제 함수
element delete_max_heap(HeapType* h) {
    int parent, child;
    element item, temp;

    item = h->heap[1];
    temp = h->heap[(h->heap_size)--];
    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;
}

int main() {
    element e1 = { 10 }, e2 = { 5 }, e3 = { 30 };
    element e4, e5, e6;
    HeapType* heap;

    heap = create();    // 히프 생성
    init(heap);         // 초기화

    // 삽입
    insert_max_heap(heap, e1);
    insert_max_heap(heap, e2);
    insert_max_heap(heap, e3);
    
    // 삭제
    e4 = delete_max_heap(heap);
    printf("< %d > ", e4.key);
    e5 = delete_max_heap(heap);
    printf("< %d > ", e5.key);
    e6 = delete_max_heap(heap);
    printf("< %d > \n", e6.key);

    free(heap);
    return 0;
}

---