우선순위 큐와 힙 (Priority Queue & Heap)
들어가는 말
우선순위 큐라는 이름을 들으면 기존에 배운 큐를 떠올리기 쉽다.
둘 다 queue, 즉 줄이나 대기열이라는 점에서는 닮았지만, 원소를 꺼내는 기준은 다르다.
일반 큐는 먼저 들어온 원소를 먼저 꺼내는 추상 자료형이고,
우선순위 큐는 들어온 원소 중 우선순위가 가장 높은 원소를 먼저 꺼내는 추상 자료형이다.
추상 자료형은 자료구조의 개념과 동작(연산)을 정의할 뿐, 원소를 실제로 저장하고 배치하는 방식까지는 정하지 않는다.
즉 우선순위 큐는 무엇을 꺼낼지만 정의할 뿐, 어떻게 저장할지는 정의하지 않는다.
따라서 우선순위 큐 자체를 선형 자료구조나 비선형 자료구조로 단정하기보다, 이를 구현하는 자료구조가 선형인지 비선형인지 구분해야 한다.
가장 먼저 배열로 구현했을 때의 한계를 살펴보자.
단순 배열 기반 구현의 한계
여기서 말하는 단순 배열은 원소 사이에 별도의 연결 관계나 계층 구조를 부여하지 않고,
인덱스를 원소의 위치를 나타내는 용도로만 사용하는 일반적인 배열을 뜻한다.
이러한 배열을 이용한 구현은 간단하지만, 삽입과 삭제, 최우선 원소 탐색을 모두 효율적으로 처리하기는 어렵다.
정렬되지 않은 배열
정렬되지 않은 배열에서는 새 원소를 배열의 끝에 추가하며, 배열 내부에 우선순위에 따른 정렬은 없다.
- 탐색: 최우선 원소를 찾으려면 모든 원소를 확인해야 하므로
O(n)이 걸린다. - 삽입: 배열의 끝에 원소를 추가하면 되므로
O(1)이 걸린다. - 삭제: 최우선 원소를 찾는 과정이 필요하므로 전체 삭제 연산은
O(n)이 걸린다.
우선순위 큐에서 삭제 대상은 임의의 원소가 아니라 우선순위가 가장 높은 원소다.
삭제 대상의 위치를 알고 있다면, 마지막 원소를 삭제 대상 위치로 옮기고 size를 하나 줄이는 방식으로 O(1)에 삭제할 수 있다.
이 방식을 swap-and-pop 또는 swap-with-last 삭제라고 한다.
하지만 정렬되지 않은 배열에서는 삭제 대상인 최우선 원소를 찾아야 한다.
모든 원소를 확인해야 하므로, 삭제에는 O(n)이 걸린다.
정렬된 배열
정렬된 배열에서는 최우선 원소를 배열의 앞이나 뒤 중 한쪽 끝에 둘 수 있다.
최우선 원소를 앞에 두는 경우
우선순위가 높을수록 배열의 앞쪽에 오도록 내림차순으로 정렬한다.
- 탐색: 최우선 원소가 배열의 첫 번째에 있으므로
O(1)에 확인할 수 있다. - 삽입: 삽입 위치를 찾은 뒤 뒤따르는 원소를 한 칸씩 옮겨야 하므로
O(n)이 걸린다. - 삭제: 첫 번째 원소를 삭제한 뒤 남은 원소를 한 칸씩 앞으로 옮겨야 하므로
O(n)이 걸린다.
최우선 원소를 뒤에 두는 경우
우선순위가 높을수록 배열의 뒤쪽에 오도록 오름차순으로 정렬한다.
- 탐색: 최우선 원소가 배열의 마지막에 있으므로
O(1)에 확인할 수 있다. - 삽입: 삽입 위치를 찾은 뒤 뒤따르는 원소를 한 칸씩 옮겨야 하므로
O(n)이 걸린다. - 삭제: 배열의 마지막 원소를 제거하면 되므로
O(1)이 걸린다.
지금 살펴본 두 가지 단순 배열 구현은 정렬 여부와 상관없이 삽입·삭제·최우선 원소 탐색 중 하나 이상에 O(n)이 걸린다는 한계를 가진다.
이러한 한계를 극복하는 방법이 완전 이진 트리(complete binary tree) 기반의 이진 힙(Binary Heap)이다.
이진 힙에서는 최우선 원소 탐색을 O(1)에 처리할 수 있고, 삽입과 최우선 원소 삭제를 모두 O(log n)에 처리할 수 있다.
힙(Heap)
힙(Heap)은 원소 삽입과 최우선 원소의 조회 및 삭제를 효율적으로 처리하기 위한 자료구조로, 주로 우선순위 큐를 구현할 때 사용된다.
힙에는 이진 힙(Binary Heap), d-항 힙(d-ary Heap), 이항 힙(Binomial Heap), 피보나치 힙(Fibonacci Heap) 등 여러 종류가 있다.
구조와 연산 방식은 서로 다르지만, 모든 힙은 부모 노드와 자식 노드 사이의 대소 관계를 규정하는 힙 속성(Heap Property)을 만족한다.
최대 힙에서는 부모 노드의 값이 자식 노드의 값보다 크거나 같고, 최소 힙에서는 작거나 같다.
이때 정해지는 것은 부모와 자식 사이의 관계뿐이며, 형제 노드 사이의 대소 관계는 정해지지 않는다.
이 글에서는 우선순위 큐 구현에 널리 사용되는 이진 힙을 다룬다.
이진 힙은 논리적으로 완전 이진 트리 구조를 가지지만, 일반적으로 배열로 구현한다.
완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 채워져 있고, 마지막 레벨의 노드가 왼쪽부터 연속적으로 배치된 트리이다.
이러한 특성 덕분에 별도의 포인터 없이 배열 인덱스만으로 부모 노드와 자식 노드의 위치를 계산할 수 있는 이점이 있다.
따라서 이 글에서는 배열을 기반으로 이진 힙을 구현한다.
최대 힙(Max Heap)
최대 힙에서는 모든 부모 노드의 값이 자식 노드의 값보다 크거나 같다.
그러므로 가장 큰 값은 루트 노드에 위치한다.
9
/ \
7 8
/ \ / \
3 5 6 2최소 힙(Min Heap)
최소 힙에서는 모든 부모 노드의 값이 자식 노드의 값보다 작거나 같다.
그러므로 가장 작은 값은 루트 노드에 위치한다.
2
/ \
3 5
/ \ / \
7 6 8 9배열을 이용한 힙 표현
완전 이진 트리는 각 레벨의 노드를 위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 채우므로 배열에 순서대로 저장할 수 있다.
이때 계산을 단순하게 하기 위해 0번 인덱스는 비워 두고, 루트 노드를 1번 인덱스에 저장한다.
노드가 배열의 인덱스 i에 저장되어 있을 때, 부모와 자식 노드의 인덱스는 다음과 같이 계산된다.
- 부모 노드:
i / 2(정수 나눗셈) - 왼쪽 자식 노드:
i * 2 - 오른쪽 자식 노드:
i * 2 + 1
앞서 본 최소 힙은 다음과 같이 배열로 나타낼 수 있다.
[0, 2, 3, 5, 7, 6, 8, 9]
0 1 2 3 4 5 6 70번 인덱스와 그 값은 사용하지 않는다.
루트 노드인 값 2는 인덱스 1에 저장되어 있다.
인덱스 1에 1 * 2를 적용하면 왼쪽 자식 노드인 값 3이 저장된 인덱스 2를 얻는다.
인덱스 1에 1 * 2 + 1을 적용하면 오른쪽 자식 노드인 값 5가 저장된 인덱스 3을 얻는다.
값 9는 배열의 마지막 인덱스인 7에 저장되어 있다.
인덱스 7에 7 / 2를 적용하면 부모 노드가 저장된 인덱스 3을 얻고, 해당 인덱스의 값은 5이다.
이처럼 배열 인덱스만으로 부모와 자식 노드의 위치를 알 수 있으므로, 별도의 포인터 없이 이진 트리 구조를 표현할 수 있다.
소스 코드
heap.h
#ifndef HEAP_H
#define HEAP_H
#include <stdbool.h>
#define HEAP_CAPACITY 128
typedef int HeapData;
typedef int (*HeapCompare)(HeapData lhs, HeapData rhs);
typedef struct Heap
{
int size;
HeapData arr[HEAP_CAPACITY + 1];
HeapCompare compare;
} Heap;
void heap_init(Heap* heap, HeapCompare compare);
bool heap_is_empty(Heap* heap);
bool heap_push(Heap* heap, HeapData data);
bool heap_pop(Heap* heap);
HeapData heap_top(Heap* heap);
#endif /* HEAP_H */heap.c
#include "heap.h"
static int get_parent_index(int index)
{
return index / 2;
}
static int get_left_child_index(int index)
{
return index * 2;
}
static int get_right_child_index(int index)
{
return index * 2 + 1;
}
static int get_higher_priority_child_index(Heap* heap, int index)
{
int left_index = get_left_child_index(index);
if (left_index > heap->size)
return 0;
if (left_index == heap->size)
return left_index;
int right_index = get_right_child_index(index);
if (heap->compare(heap->arr[left_index], heap->arr[right_index]) >= 0)
return left_index;
return right_index;
}
void heap_init(Heap* heap, HeapCompare compare)
{
heap->size = 0;
heap->arr[0] = 0;
heap->compare = compare;
}
bool heap_is_empty(Heap* heap)
{
return heap->size == 0;
}
bool heap_push(Heap* heap, HeapData data)
{
if (heap->size >= HEAP_CAPACITY)
return false;
int current_index = heap->size + 1;
while (current_index != 1)
{
int parent_index = get_parent_index(current_index);
if (heap->compare(data, heap->arr[parent_index]) <= 0)
break;
heap->arr[current_index] = heap->arr[parent_index];
current_index = parent_index;
}
heap->arr[current_index] = data;
heap->size++;
return true;
}
bool heap_pop(Heap* heap)
{
if (heap_is_empty(heap))
return false;
HeapData last_data = heap->arr[heap->size--];
int current_index = 1;
while (true)
{
int child_index = get_higher_priority_child_index(heap, current_index);
if (child_index == 0 ||
heap->compare(last_data, heap->arr[child_index]) >= 0)
break;
heap->arr[current_index] = heap->arr[child_index];
current_index = child_index;
}
heap->arr[current_index] = last_data;
return true;
}
HeapData heap_top(Heap* heap)
{
return heap->arr[1];
}priority_queue.h
#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H
#include "heap.h"
typedef HeapData PriorityQueueData;
typedef HeapCompare PriorityQueueCompare;
typedef struct PriorityQueue
{
Heap heap;
} PriorityQueue;
void priority_queue_init(PriorityQueue* pq, PriorityQueueCompare compare);
bool priority_queue_is_empty(PriorityQueue* pq);
bool priority_queue_push(PriorityQueue* pq, PriorityQueueData data);
bool priority_queue_pop(PriorityQueue* pq);
PriorityQueueData priority_queue_top(PriorityQueue* pq);
#endif /* PRIORITY_QUEUE_H */priority_queue.c
#include "priority_queue.h"
void priority_queue_init(PriorityQueue* pq, PriorityQueueCompare compare)
{
heap_init(&pq->heap, compare);
}
bool priority_queue_is_empty(PriorityQueue* pq)
{
return heap_is_empty(&pq->heap);
}
bool priority_queue_push(PriorityQueue* pq, PriorityQueueData data)
{
return heap_push(&pq->heap, data);
}
bool priority_queue_pop(PriorityQueue* pq)
{
return heap_pop(&pq->heap);
}
PriorityQueueData priority_queue_top(PriorityQueue* pq)
{
return heap_top(&pq->heap);
}main.c
#include <stdio.h>
#include "priority_queue.h"
static int compare_max_heap(HeapData lhs, HeapData rhs)
{
return lhs - rhs;
}
static int compare_min_heap(HeapData lhs, HeapData rhs)
{
return rhs - lhs;
}
static void print_priority_queue(const PriorityQueue* pq)
{
printf("array : [");
for (int i = 0; i <= pq->heap.size; i++)
{
printf("%2d ", pq->heap.arr[i]);
}
printf("]\n");
printf("index : ");
for (int i = 0; i <= pq->heap.size; i++)
{
printf("%2d ", i);
}
printf("\n");
}
int main(void)
{
PriorityQueue pq;
int values[] = { 17, 3, 42, 29, 8, 35, 14, 47 };
int count = sizeof(values) / sizeof(values[0]);
priority_queue_init(&pq, compare_min_heap);
for (int i = 0; i < count; i++)
priority_queue_push(&pq, values[i]);
print_priority_queue(&pq);
printf("pop : ");
while (!priority_queue_is_empty(&pq))
{
printf("%2d ", priority_queue_top(&pq));
priority_queue_pop(&pq);
}
printf("\n");
return 0;
}구현 설명
우선순위 큐는 최우선 원소를 꺼내는 동작을 정의하는 추상 자료형이므로, 사용자는 내부 구현을 알 필요가 없다.
따라서 PriorityQueue는 사용자에게 push, pop, top 연산을 제공하고,
내부의 Heap은 원소를 저장하며 최우선 원소를 빠르게 꺼낼 수 있도록 힙 속성을 유지한다.
데이터의 우선순위 기준은 자료구조를 구현하는 쪽보다, 데이터를 사용하는 호출자가 정하는 편이 바람직하다.
호출자가 자신이 다루는 데이터의 의미와 어떤 기준으로 정렬할지를 가장 잘 알고 있기 때문이다.
힙에 저장되는 데이터는 char, int 같은 기본 자료형에 한정되지 않고, 사진을 나타내는 구조체일 수도 있다.
이때 우선순위를 사진 속 사람 수로 정할 수도 있으므로, 어떤 값을 기준으로 삼을지는 자료구조가 아닌 호출자가 결정해야 한다.
그래서 비교 함수를 매개변수로 받아, 비교 결과가 양수이면 첫 번째 원소가 두 번째 원소보다 높은 우선순위를 가진다고 해석한다.
힙은 이 기준에 따라 부모 노드가 자식 노드보다 높은 우선순위를 가지도록 힙 속성을 유지한다.
실행 결과
compare_min_heap 함수로 실행한 결과는 다음과 같다.
array : [ 0 3 8 14 29 17 42 35 47 ]
index : 0 1 2 3 4 5 6 7 8
pop : 3 8 14 17 29 35 42 47compare_max_heap 함수로 실행한 결과는 다음과 같다.
array : [ 0 47 42 35 29 8 17 14 3 ]
index : 0 1 2 3 4 5 6 7 8
pop : 47 42 35 29 17 14 8 3삽입
새 원소를 삽입한 뒤에도 부모가 자식보다 높은 우선순위를 갖도록 힙 속성을 유지해야 한다.
먼저 개념적인 삽입 과정을 살펴보자.
새 원소를 완전 이진 트리의 마지막 위치에 추가한다.
새 원소의 우선순위가 부모보다 높으면 두 원소의 위치를 서로 바꾼다.
이러한 상향 이동(percolate up)을 새 원소가 루트에 도달하거나 부모보다 높은 우선순위를 갖지 않을 때까지 반복한다.
한 번 올라갈 때마다 현재 위치의 배열 인덱스가 절반으로 줄어들기 때문에 삽입의 시간 복잡도는 O(log n)이다.
실제 heap_push는 같은 결과를 만들지만, 새 원소와 부모를 반복해서 교환하지는 않는다.
먼저 완전 이진 트리의 마지막 위치인 heap->size + 1을 새 원소를 저장할 후보 위치로 정한다.
새 원소는 배열에 바로 저장하지 않고 data 매개변수에 둔 채 부모와 우선순위를 비교한다.
data의 우선순위가 더 높으면 부모 원소를 현재 후보 위치에 복사한다.
이때 배열에는 같은 부모 원소가 두 위치에 일시적으로 존재한다.
그런 다음 current_index를 parent_index로 변경하여 부모가 있던 위치를 새 원소의 다음 저장 후보로 정한다.
루트에 도달하거나 data의 우선순위가 부모보다 높지 않으면 반복을 멈추고, 최종 후보 위치에 data를 저장한다.
마지막으로 size를 증가시키면 삽입이 완료된다.
삭제
최우선 원소를 삭제한 뒤에도 부모가 자식보다 높은 우선순위를 갖도록 힙 속성을 유지해야 한다.
먼저 개념적인 삭제 과정을 살펴보자.
루트에 있는 최우선 원소를 삭제하고, 완전 이진 트리의 마지막 원소를 루트로 옮긴다.
루트로 옮긴 원소의 우선순위가 자식보다 낮으면 우선순위가 더 높은 자식과 위치를 서로 바꾼다.
자식이 둘이라면 두 자식 중 우선순위가 더 높은 원소를 선택해야 한다.
이러한 하향 이동(percolate down)을 단말 노드에 도달하거나 자식보다 낮은 우선순위를 갖지 않을 때까지 반복한다.
한 번 내려갈 때마다 트리의 레벨을 하나씩 이동하기 때문에 삭제의 시간 복잡도는 O(log n)이다.
실제 heap_pop은 같은 결과를 만들지만, 마지막 원소와 자식을 반복해서 교환하지는 않는다.
먼저 마지막 원소를 last_data 지역 변수에 저장하면서 size를 감소시킨다.
루트 인덱스인 1을 last_data를 저장할 후보 위치로 정하고,
get_higher_priority_child_index 함수로 현재 위치의 자식 중 우선순위가 더 높은 원소를 찾는다.
last_data보다 자식의 우선순위가 더 높으면 해당 자식을 현재 후보 위치에 복사한다.
이때 배열에는 같은 자식 원소가 두 위치에 일시적으로 존재한다.
그런 다음 current_index를 child_index로 변경하여 자식이 있던 위치를 last_data의 다음 저장 후보로 정한다.
현재 위치에 자식이 없거나 last_data의 우선순위가 선택한 자식보다 높거나 같으면 반복을 멈추고, 최종 후보 위치에 last_data를 저장한다.