티스토리 뷰

그래프 - 트리 ( Tree )

힙 ( heap )

RiKang 2017.12.15 22:18

Table of Contents


개요

기본 구조

값 삽입

최대값 삭제

힙 정렬

C++ STL priority_queue




1. 개요


 힙은 이진 트리를 활용한 자료구조이며, 종류로는 최소 힙과 최대 힙이 있습니다. 최대 힙을 알면 최소 힙을 만드는 건 어렵지 않으므로, 이 문서에서는 최대 힙을 기준으로 설명하도록 하겠습니다.


 최대 힙 자료구조는 기본적으로 아래의 세 연산을 빠르게 수행하기 위한 자료구조입니다.


연산 1) 최대 힙에 새로운 값을 삽입. 

연산 2) 최대 힙 안의 최대값을 삭제.

연산 3) 최대 힙 안의 값 중에 최대값 찾기.


 이 세 연산을 배열로 간단하게 처리하려고 하면, 삽입은 O(1)로 가능하더라도 최대값을 찾기에서 O(N) 이 필요함을 알 수 있습니다. 배열에서 최대값을 찾기 위해선, 배열 안의 모든 값을 조사하는 선형 검색이 필요하기 떄문이지요. 반면에 힙은 이 세 개의 연산을 모두 빠르게 수행하기 위해 사용하는 자료구조로서 삽입과 삭제는 O(log N), 최대값 찾기는 O(1)로 가능합니다.




2. 기본 구조


 힙의 기본 구조는 아래와 같은 세 가지의 규칙을 준수하는 이진트리입니다.


규칙 1) 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소보다 크거나 같아야 한다.

규칙 2) 마지막 레벨을 제외한 레벨에서는 노드가 모두 채워져야 한다.

규칙 3) 마지막 레벨에서 노드는 왼쪽부터 채워져야 한다.


 이 세 규칙을 만족하는 예시는 다음과 같습니다.





규칙 1. 부모 노드의 원소가 자식 노드의 원소 이상입니다. (루트 노드의 경우 : 9>7, 9>6)

규칙 2. 레벨0는 노드가 1개, 레벨1은 2개로 모두 채워져 있습니다. (이진 트리이므로 더 많은 노드를 넣을 순 없습니다.)

규칙 3. 레벨2는 왼쪽부터 순서대로 채워져, 결국 제일 오른쪽만 비어있습니다.


 이와 같이 엄격한 규칙 덕분에, 힙은 단순히 배열을 이용해도 쉽게 구현할 수 있습니다. 루트 노드의 원소 값은 H[0], 루트 노드의 자식 노드들은 H[1], H[2], ...., 이런 식으로 레벨순, 그리고 레벨이 같다면 왼쪽부터 원소 값을 저장하면 간선을 따로 저장하지 않아도 되기 때문이지요. 아래의 예시를 잘 살펴보면 세 가지 특징을 확인하실 수 있습니다.




특징 1) N 개의 원소가 있을 경우, H[0] ~ H[N-1] 이 그 값을 저장한다.

특징 2) H[i] 의 자식 노드는 H[2*i+1], H[2*i+2] 이다.

특징 3) H[i] 의 부모 노드는 H[(i-1)/2] 이다.


이 3가지 특성을 종합하면 간선을 따로 저장할 필요가 없음을 알 수 있습니다. 부모 노드와 자식 노드가 누군지 수식을 통해 알 수 있기 때문입니다. 따라서 아래와 같이 힙의 기본 구조를 잡을 수 있습니다.


1
2
3
4
5
6
7
8
9
//code by RiKang, weeklyps.com
struct max_heap{
    vector<int> h;       // 원소값들을 저장한다. h[i] 의 자식 = h[2*i+1], h[2*i+2]
    void push(int v){}   // 힙에 v를 삽입한다.
    int top(void){       // 힙에서 최대값을 반환한다.
        return h[0];
    }
    void pop(void){}     // 힙에서 최대값을 삭제한다.
}mh;
cs


 그리고 힙의 규칙1 (부모 노드의 값은 자식 노드의 값보다 크거나 같아야 한다.)로 인해, 루트 노드의 값이 최대값인 것은 자명하므로 최대값을 반환할 땐 h[0] 을 반환하면 됩니다. 이 최대값 찾기의 시간복잡도는 O(1)입니다.




3. 값 삽입


 힙은 값의 삽입을 O(log N)으로 해결합니다. 삽입을 할 때에는 힙의 규칙에 유의해야 합니다. 당연한 이야기이지만, 원소의 삽입 이후에도 힙의 규칙들이 모두 준수되어야 하기 때문입니다.


 힙의 규칙을 유지하면서, O(log N)으로 삽입을 마치는 알고리즘은 아래와 같습니다.


step 1) 힙의 맨 끝에 삽입할 값을 넣는다.

step 2) 삽입한 값이 부모 노드의 값보다 크면 두 값을 서로 바꾼다.

step 3) 삽입한 값이 루트 노드에 도달하였거나, 삽입한 값보다 큰 부모 노드의 값을 만날 때 까지 2를 반복한다.




 알고리즘에 따라, 예시에 나왔던 힙에 10을 삽입하여 보겠습니다.


 1. 힙의 맨 끝에 삽입할 값을 넣는다.




 2. 삽입한 값이 부모 노드의 값보다 크면 두 값을 서로 바꾼다. (10 > 6 이니 서로 바꿔주어야 합니다.)



2. 삽입한 값이 부모 노드의 값보다 크면 두 값을 서로 바꾼다. (10 > 9이니 서로 바꿔주어야 합니다.)



3. 삽입한 값이 루트 노드에 도달하였거나, 삽입한 값보다 큰 부모 노드의 값을 만날 때 까지 2를 반복한다.

   -> 삽입한 10이 루트 노드에 도달하였기 때문에 반복을 종료합니다.


 이처럼 삽입 과정을 완료하면 힙의 규칙이 지켜지면서 삽입이 완료됩니다.


규칙 1. 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소보다 크거나 같아야 한다.

-> 부모 노드가 삽입한 값보다 크거나, 부모 노드가 없을 때 까지 반복하였기 때문에 성립합니다.


규칙 2.  마지막 레벨을 제외한 레벨에서는 노드가 모두 채워져야 한다.

-> 처음 삽입할 때, 힙의 맨 끝에 노드를 추가하였기 때문에 성립합니다.


규칙 3.  마지막 레벨에서 노드는 왼쪽부터 채워져야 한다.

-> 처음 삽입할 때, 힙의 맨 끝에 노드를 추가하였기 때문에 성립합니다.


 아래는 기본 구조에 삽입까지 구현한 코드입니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//code by RiKang, weeklyps.com
struct max_heap{
    vector<int> h;       // 원소값들을 저장한다. h[i] 의 자식 = h[2*i+1], h[2*i+2]
    void push(int v){    // 힙에 v를 삽입한다.
        int idx = h.size(); // idx = 삽입한 값이 들어있는 위치
        h.push_back(v);
        while(idx!=0 && h[idx]>h[(idx-1)/2]){ // idx가 루트 노드이거나, 부모 노드 값이 v 이상이면 반복 종료한다.
            swap(h[idx], h[(idx-1)/2]);
            idx = (idx-1)/2;
        }
    }
    int top(void){       // 힙에서 최대값을 반환한다.
        return h[0];
    }
    void pop(void){}     // 힙에서 최대값을 삭제한다.
}mh;
cs




4. 최대값 삭제


 힙은 값의 삽입과 마찬가지로 최대값의 삭제도 O(log N) 으로 해결할 수 있습니다. 물론 힙의 규칙은 준수되어야 합니다. 힙의 규칙을 유지하면서, O(log N)으로 최대값의 삭제를 마치는 알고리즘은 아래와 같습니다.


step 1) 힙의 끝에 있던 값을 루트 노드에 넣는다. (루트 노드에 있던 최대값은 자연스럽게 삭제됩니다.)

step 2) idx = 0 으로 설정한다. (idx = 루트 노드)

step 3) idx의 자식 노드의 값 중 큰 값과 idx에 있는 값을 비교한다.

step 4) step 3에서 자식 노드의 값이 더 크면 두 값을 서로 바꾸고 idx를 해당 자식 노드로 변경한 후, step 3으로 돌아간다.

step 5) step 3에서 idx에 있는 값이 더 크거나 같으면, 혹은 자식 노드가 없으면 알고리즘을 종료한다.



 알고리즘에 따라 위의 예시에서 최대값인 9를 삭제해보겠습니다.


1. 힙의 끝에 있던 값을 루트 노드에 넣는다. (루트 노드에 있던 최대값은 자연스럽게 삭제됩니다.)




2. idx = 0 으로 설정한다. (idx = 루트 노드)

3. idx의 자식 노드의 값 중 큰 값과 idx에 있는 값을 비교한다. ( 7 > 2 이므로 step 4로 갑니다.)

4. step 3에서 자식 노드의 값이 더 크면 두 값을 서로 바꾸고 idx를 해당 자식 노드로 변경한 후, step 3으로 돌아간다.




3. idx의 자식 노드의 값 중 큰 값과 idx에 있는 값을 비교한다. ( 5 > 2 이므로 step 4로 갑니다.)

4. step 3에서 자식 노드의 값이 더 크면 두 값을 서로 바꾸고 idx를 해당 자식 노드로 변경한 후, step 3으로 돌아간다.




3. idx의 자식 노드의 값 중 큰 값과 idx에 있는 값을 비교한다. ( 더 이상 자식 노드가 없으므로 step 5로 갑니다.)

5. step 3에서 idx에 있는 값이 더 크거나 같으면, 혹은 자식 노드가 없으면 알고리즘을 종료한다.


 이처럼 삭제 과정을 완료하면 힙의 규칙이 지켜지면서 삭제가 완료됩니다.


규칙 1. 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소보다 크거나 같아야 한다.

-> 자식 노드가 삽입한 값보다 작거나, 자식 노드가 없을 때 까지 반복하였기 때문에 성립한다.


규칙 2.  마지막 레벨을 제외한 레벨에서는 노드가 모두 채워져야 한다.

-> 처음 삭제할 때, 힙의 맨 끝에 노드를 삭제한 꼴이기 때문에 성립합니다.


규칙 3.  마지막 레벨에서 노드는 왼쪽부터 채워져야 한다.

-> 처음 삭제할 때, 힙의 맨 끝에 노드를 삭제한 꼴이기 때문에 성립합니다.


 이를 구현하면 아래와 같이 됩니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//code by RiKang, weeklyps.com
struct max_heap{
    vector<int> h;       // 원소값들을 저장한다. h[i] 의 자식 = h[2*i+1], h[2*i+2]
    void push(int v){    // 힙에 v를 삽입한다.
        int idx = h.size(); // idx = 삽입한 값이 들어있는 위치
        h.push_back(v);
        while(idx!=0 && h[idx]>h[(idx-1)/2]){ // idx가 루트 노드이거나, 부모 노드 값이 v 이상이면 반복 종료한다.
            swap(h[idx], h[(idx-1)/2]);
            idx = (idx-1)/2;
        }
    }
    int top(void){       // 힙에서 최대값을 반환한다.
        return h[0];
    }
    void pop(void){      // 힙에서 최대값을 삭제한다.
        h[0= h.back(); // 힙의 끝에 있던 값을 루트에 넣는다.
        h.pop_back();    // 의미가 없어진 힙의 끝은 삭제한다.
        int idx = 0;
        while(true){
            int child = 2*idx+1;         // child = 왼쪽 자식
            if(child >= h.size()) break// 자식 노드가 없는 경우, 종료
            if(child+1 < h.size() && h[child+1> h[child])
                child++;                 // 오른쪽 자식이 왼쪽 자식보다 클 경우, 오른쪽 자식으로 child를 변경
            if(h[idx] >= h[child]) break;// 자식의 값보다 idx의 값이 더 크거나 같을 경우, 종료.
            swap(h[idx], h[child]);      // 자식의 값이 더 클 경우, 스왑.
            idx = child;
        }
    }
}mh;
cs




5. 힙 정렬


 힙의 간단한 응용으로 유명한 것이 힙 정렬입니다. 정렬을 할 때 힙을 사용하면 손쉽게 O(N log N)의 정렬을 할 수 있습니다.


1. 힙에 모든 값을 삽입한다.

2. 힙에서 최대값을 출력한다.

3. 힙에서 최대값을 삭제한다.

4. 힙에서 모든 값이 삭제될 때까지 2,3을 반복한다.


 이를 통해, 아래의 문제를 해결해보도록 하겠습니다.







6. C++ STL priority_queue


 C++ STL 에는 힙이 구현되어 있는 자료구조가 있습니다. 우선순위 큐라고 부르고 priority_queue<> 의 형식으로 사용하며, push, top, pop 연산을 지원합니다. priority_queue를 기본 형식으로 선언하면 최대힙으로 설정됩니다.


 사용시에는 전처리문으로 #include<queue> 가 들어가야 합니다.


 이를 활용해 위의 힙 정렬 문제를 해결하면 아래와 같이 됩니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
 
using namespace std;
 
priority_queue<int> pq;
 
int main() {
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        int v;
        scanf("%d",&v);
        pq.push(-v);
    }
    for(int i=0; i<n; i++){
        printf("%d\n",-pq.top());
        pq.pop();
    }
    return 0;
}
cs


 최소 힙으로 사용하고 싶은 경우, priority_queue<int, vector<int>, greater<int> > 의 형식을 사용하면 간편합니다.


 이 형식에서 vector<int> 는 우선순위 큐 내부 구조에서 사용할 자료구조를 설정한 것이며, greater<int> 는 비교 연산에서 사용할 연산을 설정한 것입니다. greater<int> 로 인해 자연스럽게 최소 힙으로 설정되는 것입니다. 물론, int를 제외한 다른 변수형들도 가능합니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
priority_queue<intvector<int>, greater<int> > pq;
int main() {
    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++){
        int v;
        scanf("%d",&v);
        pq.push(v);
    }
    for(int i=0; i<n; i++){
        printf("%d\n",pq.top());
        pq.pop();
    }
    return 0;
}
cs

※ 본문의 코드들은 C++ 14 환경으로 작성되었습니다.


'그래프 - 트리 ( Tree )' 카테고리의 다른 글

힙 ( heap )  (0) 2017.12.15