트리 - 우선순위 큐와 힙

* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 23장 우선순위 큐와 힙에 나온 내용을 바탕으로 작성하였습니다.

 

개요

 

우리는 기존에 "큐(Queue)"라는 자료구조를 배웠었다.

큐는 스택과 비슷한 자료구조로 '선입선출'이라는 형태를 갖추고 있다.

 

그렇다면 우선순위 큐와 큐의 차이점은 무엇일까?

바로 '우선순위', 즉 선입선출 구조이나 '우선순위'대로 원소를 꺼낼 수 있다는 점이다.

 

우선순위를 만족하게 정렬하려면 여러가지 방법이 있다.

가장 단순한 방법은 O(n)이라는 시간에 모든 원소를 비교해서 정렬할 수 있다. 하지만 당연히 이 방법은 사용하지 않을 것이다.

 

이진 탐색 트리(Binary Search Tree)를 사용하면 O(logn)의 시간에 정렬할 수 있지만 이는 책의 표현을 빌려 쓰자면 "닭 잡는데 소 잡는 칼을 사용하는 격"이다.

 

그렇다면 가장 좋은 방법은 바로 "힙"으로 구현하는 것이다.

 

힙(Heap)역시 자료구조 시간에 이미 배웠지만 다시 공부해 보자.

 

1. 힙의 정의와 구현

 

(내가 공부할 것은 Max Heap이다.)

 

먼저 힙의 루트에는 항상 트리에서 가장 큰 원소가 위치한다.

그리고 트리의 높이를 일정하게 유지하기 위해 두 가지 제약 조건을 둔다.

 

1. 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다.

2. 마지막 레벨에 노드가 있을 때는 항상 가장 왼쪽부터 순서대로 채워져 있어야 한다.

 

뭔가 균형 잡인 이진트리(완전 이진트리)와 비슷한 느낌이 든다..

 

이제 힙을 구현해보자.

 

힙은 한 개의 배열로 구현이 가능하다고 한다.

이유는 힙의 엄격한 모양 규칙때문이다.

 

이제 배열에 원소를 순서대로 채워보자. 

그렇게 하면 아래 그림과 같은 트리가 나오게 된다.

 

아래 그림을 보자.

 

이 그림을 통해 알 수 있는 점이 3가지가 있다.

 

1. A[i]에 대응되는 노드의 왼쪽 자손은 A[2*i+1]에 대응됩니다.

2. A[i]에 대응되는 노드의 오른쪽 자손은 A[2*i+2]에 대응됩니다.

3. A[i]에 대응되는 노드의 부모는 A[(i-1)/2]에 대응됩니다. (나눗셈 결과는 내림)

 

즉, 이 규칙에 의해 힙의 모든 원소들은 순차적으로 대응됨을 알 수 있다.

 

이제 힙에 새 원소를 삽입하여 보자.

 

나도 처음에는 힙의 루트에 삽입한 후 비교하면서 내려가야 될 것이다 라고 생각했었다.

그래서 처음에 힙이 왜 시간 복잡도적인 측면에서 이득인지 궁금증이 들었었다.

 

하지만 힙의 새 원소 삽입은 루트부터 시작하지 않는다.

힙의 가장 중요한 '모양 규칙'에 따라 제일 마지막, 즉 모양 규칙에 의해 새로운 노드가 생성되어야 할 곳에 삽입된다.

 

이렇게 하면 모양 규칙도 만족하게 되고, 거꾸로 루트까지 올라가면서 비교하면 된다.

 

아래는 힙에서의 삽입 코드이다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
// 정수를 담는 최대 힙 heap에 새 원소 newValue삽입
void push_heap(vector<int>& heap, int newValue) {
    // 힙의 맨 끝에 newValue삽입 -> heap이 vector로 구현되어 있음
    heap.push_back(newValue);
    // newValue의 위치는 heap의 가장 마지막 index이다.
    int idx = heap.size() - 1;
    // 루트에 도달하거나 newValue 이상의 원소를 가진 조상을 만날 때 까지
    while (idx > 0 && heap[(idx - 1) / 2] < heap[idx]) {
        // 부모 노드보다 값이 더 크다면 부모 노드와 위치를 바꿔줌
        swap(heap[idx], heap[(idx - 1) / 2]);
        idx = (idx - 1) / 2; // 부모 노드의 index값
    }
}

while문이 최대 힙의 높이까지만 작동하기 때문에 이 코드의 시간 복잡도는 O(log n) 임을 알 수 있다.

 

이제 최대 원소를 꺼내보자.

 

최대 원소를 찾는 것은 매우 매우 쉽다. 

Max Heap에서는 루트에 무조건 최대 원소가 존재한다. (힙의 정의)

 

문제는 이 루트를 힙에서 꺼내는 것이다.

이유는 루트 노드를 지우면서 엄격한 모양 규칙을 유지해야 하기 때문이다.

 

힌트는 이미 우리가 구현했던 힙에 원소 삽입에 있다.

힙의 제일 마지막 노드는 모양 규칙에 의해 어차피 삭제될 노드이다.

그렇다면 이 마지막 노드의 원소는 어디로 가야 할까?

바로 루트 노드이다.

 

루트 노드와 리프 노드의 원소를 바꿔주고, 리프 노드를 삭제하면 된다.

이후에는 트리의 바닥에 도달하거나 두 자식 노드보다 값이 클 때까지 반복문을 진행하면 된다.

 

아래 코드는 최대 힙에서의 pop코드이다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
// Max Heap에서 heap[0]을 제거
void pop_heap(vector<int>& heap) {
    // 힙의 맨 끝의 값을 루트 노드의 값으로 덮어쓴다
    heap[0] = heap.back();
    // 마지막 노드를 제거함으로써 모양 규칙 성립
    heap.pop_back();
    // 루트 노드부터 시작
    int here = 0;
    while (true) {
        int left = here * 2 + 1; // 왼쪽 자식 노드
        int right = here * 2 + 2; //오른쪽 자식 노드
        // 리프노드에 도착한 경우(맨 마지막 노드)
        if (left >= heap.size())break;
        // heap이 내려갈 자리 찾기
        int next = here;
        // 왼쪽 자식과 오른쪽 자식의 값들이 자신보다 작은지 판단
        if (heap[next] < heap[left]) next = left;
        if (right < heap.size() && heap[next] < heap[right]) next = right;
        if (next == here) break;
        swap(heap[here], heap[next]);
        here = next;
    }
}

삽입과 거의 비슷한 것을 알 수 있다.

 

여기까지 힙에 대해 알아보았다.

 

사실 힙에 대해 알아본 이유는 우선순위 큐 때문이었다.

 

이를 통해 우선순위 큐는 힙으로 이루어져 있음을 알 수 있다.

그만큼 효율적이고 빠른 시간 안에 원소의 삽입과 정렬이 가능함을 알 수 있다.

 

우리는 편리하게도 C++의 STL 중 #include <queue>를 통해 우선순위 큐를 사용할 수 있다.

 

priority_queue <자료형, 컨테이너, 비교자> pq; 로 사용 가능하다.

자세한 내용은 구글링을 통해..