힙(Heap)과 우선순위 큐(Priority Queue)

힙이란?

• 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 다음과 같은 규칙을 갖는 완전이진트리를 기본으로 한 자료구조
  • A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
• 힙에는 두가지 종류가 있다.
  • 최대 힙: 부모노드의 키 값이 자식노드의 키 값보다 항상 큰 힙
  • 최소 힙: 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙
• 대부분의 경우는 자식노드의 개수가 최대 2개인 이진 힙(binary heap)을 사용
• 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 루트 노드에 오게 되는 특징이 있음
• 이를 응용하여 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

힙의 주요 연산

최소 힙을 기준으로 힙의 주요 연산은 다음과 같다.

• build_min_heap(h) : 배열을 최소 힙으로 만듦
• min_heapify(h, k, n) : 크기가 n인 배열에 k번 노드가 루트 노드인 트리를 최소 힙으로 만듦
• insert_heap(h, item) : 최소 힙 h에 원소 item을 삽입
• extract_min(h) : 최소 힙 h의 최소 원소를 반환한 다음 삭제

---

힙 구현

최소 힙을 기준으로 구현하였다.

#define HEAP_SIZE 10
typedef struct {
    char* node_name;
    int key;
} Node;
typedef struct {
    Node arr[HEAP_SIZE];
    int size;
} Heap;
void init_heap(Heap* heap) {
    heap->size = 0;
}
void swap(Node* a, Node* b) {
    Node tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
void min_heapify(Heap* heap, int k, int n) {
    int left = 2 * k, right = 2 * k + 1, smaller;
    if (right < n) {
        smaller = heap->arr[left].key < heap->arr[right].key ? left : right;
    }
    else if (left < n) {
        smaller = left;
    }
    else return;
    if (heap->arr[smaller].key < heap->arr[k].key) {
        swap(&heap->arr[smaller], &heap->arr[k]);
        min_heapify(heap, smaller, n);
    }
}
void build_min_heap(Heap* heap) {
    for (int i = (heap->size - 1) / 2; i >= 0; i--) {
        min_heapify(heap, i, heap->size);
    }
}
void insert_heap(Heap* heap, Node item) {
    heap->arr[heap->size++] = item;
    int i = heap->size - 1;
    while (i > 0 && heap->arr[i / 2].key > heap->arr[i].key) {
        swap(&heap->arr[i / 2], &heap->arr[i]);
        i /= 2;
    }
}
Node extract_min(Heap* heap) {
    Node root = heap->arr[0];
    heap->arr[0] = heap->arr[--heap->size];
    min_heapify(heap, 0, heap->size);
    return root;
}

구조체 Node에서 node_name이 아닌 key 값의 크기에 따라 어떤 값이 먼저 나와야 할지 정할 수 있다.

또한 main 함수에서 다음과 같이 힙을 채우면 build_min_heap 연산을 사용하지 않을 수 있다.

#include <stdio.h>
main() {
    Heap heap;
    init_heap(&heap);
    for (int i = 0; i < HEAP_SIZE; i++) {
        Node n;
        n.key = HEAP_SIZE - i;
        insert_heap(&heap, n);
    }
    for (int i = 0; i < HEAP_SIZE; i++) {
        Node extracted_node = extract_min(&heap);
        printf("%d ", extracted_node.key);
    }
}

하지만 다음과 같이 힙을 구성한다면 build_min_heap 연산을 사용해야 한다.

#include <stdio.h>
main() {
    Heap heap;
    init_heap(&heap);
    for (int i = 0; i < HEAP_SIZE; i++) {
        Node n;
        n.key = HEAP_SIZE - i;
        heap.arr[i] = n;
        heap.size++;
    }
    build_min_heap(&heap);
    for (int i = 0; i < HEAP_SIZE; i++) {
        Node extracted_node = extract_min(&heap);
        printf("%d ", extracted_node.key);
    }
}

위의 두 main 함수를 실행해보면 원소가 오름차순으로 출력되는 것을 확인할 수 있는데 이를 이용하여 힙정렬을 구현할 수 있다.

#include <stdio.h>
void heap_sort(Heap* heap) {
    build_min_heap(heap);
    for (int i = heap->size - 1; i > 0; i--) {
        swap(&heap->arr[0], &heap->arr[i]);
        min_heapify(heap, 0, i);
    }
}
main() {
    Heap heap;
    init_heap(&heap);
    for (int i = 0; i < HEAP_SIZE; i++) {
        Node n;
        n.key = HEAP_SIZE - i;
        insert_heap(&heap, n);
    }
    heap_sort(&heap);
    for (int i = 0; i < HEAP_SIZE; i++) {
        printf("%d ", heap.arr[i].key);
    }
}

최소 힙으로 힙을 구현했기 때문에 내림차순으로 정렬됐는데 최대 힙으로 힙을 구현한다면 오름차순으로 정렬된다.

힙정렬은 시간복잡도는 최적, 평균, 최악의 경우 큰 차이 없이 O(n*log(n))이며 안정성을 만족하지 않는 정렬이다.

---

우선순위 큐(Priority Queue)

위의 힙을 이용하여 우선순위 큐(Priority Queue)를 구현할 수 있다.

#include <stdio.h>
#define HEAP_SIZE 10
typedef struct {
    int node_num, key;
} Node;
typedef struct {
    Node arr[HEAP_SIZE];
    int size;
} PriorityQueue;
void init_queue(PriorityQueue* pqueue) {
    pqueue->size = 0;
}
void swap(Node* a, Node* b) {
    Node tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
void min_heapify(PriorityQueue* pqueue, int k, int n) {
    int left = 2 * k, right = 2 * k + 1, smaller;
    if (right < n) {
        smaller = pqueue->arr[left].key < pqueue->arr[right].key ? left : right;
    }
    else if (left < n) {
        smaller = left;
    }
    else return;
    if (pqueue->arr[smaller].key < pqueue->arr[k].key) {
        swap(&pqueue->arr[smaller], &pqueue->arr[k]);
        min_heapify(pqueue, smaller, n);
    }
}
void enqueue(PriorityQueue* pqueue, Node item) {
    pqueue->arr[pqueue->size++] = item;
    int i = pqueue->size - 1;
    while (i > 0 && pqueue->arr[i / 2].key > pqueue->arr[i].key) {
        swap(&pqueue->arr[i / 2], &pqueue->arr[i]);
        i /= 2;
    }
}
Node dequeue(PriorityQueue* pqueue) {
    Node root = pqueue->arr[0];
    pqueue->arr[0] = pqueue->arr[--pqueue->size];
    min_heapify(pqueue, 0, pqueue->size);
    return root;
}
int is_empty(PriorityQueue* pqueue) {
    return pqueue->size == 0;
}
int size(PriorityQueue* pqueue) {
    return pqueue->size;
}
main() {
    PriorityQueue pqueue;
    init_queue(&pqueue);
    for (int i = 0; i < HEAP_SIZE; i++) {
        Node n;
        n.node_num = i + 1;
        n.key = HEAP_SIZE - i;
        enqueue(&pqueue, n);
    }
    for (int i = 0; i < HEAP_SIZE; i++) {
        Node extracted_node = dequeue(&pqueue);
        printf("%d ", extracted_node.node_num);
    }
}