반응형


목차 


1. 힙(Heap)이란? 


2. 최대 힙(Max Heap) / 최소 힙(Min Heap)


3. 최대 힙, 최소 힙 삽입, 삭제 원리


4. 최대 힙 / 최소 힙 구현


5. Priority Queue


6. 힙 관련문제





** 읽기에 앞서 이 게시물을 통해 힙을 완벽하게 이해 할 수 있으니 글이 조금 길더라도 끝까지 읽어보라고 말씀드리고 싶습니다. **




1. 힙(Heap)이란?


힙(Heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(Complete binary tree)를 기본으로 한 자료구조(tree-based structure)이다.


힙을 왜 쓰는지 생각해보자.


우리는 배열을 통해 최댓값을 찾으려면 O(N)의 시간에 찾을 수 있다.


하지만 힙을 이용한다면 최댓값 혹은 최솟값을 O(lgN)에 찾을 수 있게 된다.


최악의 경우가 생겨도 힙은 완전 이진 트리이므로 항상 O(lgN)의 시간에 해결 될 수 있도록 해준다.


힙은 다양한 경우에 쓰이지만 최솟값이라는 원리를 잘 이용하면 최단거리(Dijkstra Algorithm)를 구하거나 최소 스패닝 트리(Prim Algorithm)등등에 유용하게 쓰일 수 있다.






2. 최대 힙(Max Heap) / 최소 힙(Min Heap)


최대 힙은 완전 이진트리의 root 부분에 최댓값이 항상 존재하게 되고 최소 힙은 완전 이진트리의 root 부분에 최솟값이 항상 존재하게 된다.




최대 힙의 특성은 다음과 같다.


1. 임의의 subtree에서 root가 되는 노드를 잡으면 항상 subtree에서의 root노드는 그 subtree에서 최댓값을 유지한다.


아래 그림에서 10이 root가 되는 트리를 보면 10, 9, 5, 1, 2중 10이 최대를 유지함을 알 수 있다.

(어떤 subtree에서도 똑같이 subtree의 root노드가 최댓값을 가짐을 볼 수 있다.)









최소 힙의 특성은 다음과 같다.


1. 임의의 subtree에서 root가 되는 노드를 잡으면 항상 subtree에서의 root노드는 그 subtree에서 최솟값 유지한다.


아래 그림에서 2가 root가 되는 트리를 보면 2, 5, 4, 50, 100중 2가 최소를 유지함을 알 수 있다.

(어떤 subtree에서도 똑같이 subtree의 root노드가 최솟값을 가짐을 볼 수 있다.)







이때 주의해야 할 점은 힙의 자식 노드에서 작은 것이 왼쪽, 큰 것이 오른쪽 이런것은 존재하지 않는다.

(즉, 왼쪽 오른쪽에 무슨 노드가 오건 관계없이 해당하는 subtree에서 루트노드보다 큰(minheap에서는 작은) 값이면 된다.)






3. 최대 힙, 최소 힙 삽입, 삭제 원리


** 매우 많은 그림으로 최대 힙을 알려주고자 합니다.


이 게시물을 잘 따라온다면 힙을 완벽하게 이해 할 수 있습니다.




이 게시물에서는 최대 힙에 대해 다루고자 한다.


** 왜 최소힙은 다루지 않나요? **


-> 최소 힙은 최대 힙으로 구성하고 음수(-)값으로 힙을 구현해주면 된다.




즉, 아래 그림중 14, 12, 7, 10, 8, 6이 있는데 저 값을 모두 -로 바꾸면 최대 힙에서 14가 루트에 있었지만, 


-14, -12, -7, -10, -8, -6이라면 -6이 최대 힙에서 루트에 있게 된다.(즉, 최대 힙 최소 힙의 차이는 -유무이다.)



우선 힙에서 삽입 삭제 원리를 파악하기 전에 배열을 이용한 힙을 만들고자 한다.


포인터로 힙을 구성해도 되지만 배열로 하면 index를 이용하여 매우 편하고 간단하게 힙을 제작 할 수 있다.



위의 그림에서 주황색이 배열의 index 번호라 생각해보자.


1번 인덱스 자식은 2번과 3번이고, 2번 인덱스 자식은 4번과 5번, 3번은 6번과 7번... 이다.


그렇다면 k번 인덱스의 자식은 몇번 몇번일까?


왼쪽 자식은 분명히 2*k번일 것이고 오른쪽 자식 2*k+1번이 될 것이다.




위의 그림을 보면 배열 속에서 자식이 어떻게 구성되고 있는지 좀 더 쉽게 파악 할 수 있다.


트리를 배열로 구성하면 위의 과정처럼 된다는 것을 인지하고 힙의 삽입 / 삭제 원리를 생각해보자.





최대 힙 삽입 원리(push)





위와 같이 최대 힙이 구성되어 있다 생각해보자. (검정색 숫자는 노드가 가지는 value이고 주황색 숫자는 배열 index 번호이다.)


여기서 30을 넣는다 생각해보자.




그럼 30은 우선적으로 힙의 마지막 위치에 삽입되게 된다.



하지만 저렇게 내버려두면 위에서 적어둔 최대 힙의 특성을 만족하지 못한다.


위에 적어둔 내용을 다시 한번 여기서 보자.


최대 힙의 특성은 다음과 같다.


1. 임의의 subtree에서 root가 되는 노드를 잡으면 항상 subtree에서의 root노드는 그 subtree에서 최댓값을 유지한다.



따라서 10이 root인 subtree에서 10의 자식은 30인데 10이 최댓값을 유지하지 못하고 있음을 볼 수 있다.


따라서 우리는 10과 30을 교환해줄 것이다.


(이 교환 방법은 아래 최대 힙 코드에서 기술할 것인데 매우 쉬우니 걱정하지 않아도 된다.)


10과 30을 서로 교환 한 후 다시 30의 부모노드인 12에서 보았을 때 최대힙의 특성을 만족하지 못한다.


따라서 우리는 또 12와 30을 교환해준다.



이번에도 30의 부모인 20을 보았는데 20을 root로하는 subtree에서 30은 20보다 크기에 최대 힙 특성을 만족하지 못하고 있다.


따라서 30과 20을 swap을 해준다.



마지막으로 30의 부모는 없고 30이 현재 트리의 root이므로 최대 힙 삽입과정을 마치게 된다.



30을 삽입하고 swap을 통해 완성된 최대 힙을 관찰해보면 최대 힙의 특성을 잘 만족하고 있음을 파악 할 수 있다.



이번에는 15를 한번 더 삽입해보자.



이번에도 마찬가지로 최대 힙의 마지막 위치에 삽입해준다.



12가 루트로 하는 subtree를 보니 15는 12보다 값이 크다. 따라서 최대 힙의 특성을 만족하지 못하고 있다.


따라서 우리는 12와 15를 swap해주어야 한다.


이번에는 20을 root로 하는 subtree를 보니 최대 힙의 조건을 잘 만족하고 있다.


따라서 15와 20을 따로 swap해주지 않아도 되고 여기서 최대 힙 삽입 과정을 마칠 수 있게된다.






최대 힙 삭제 원리(pop)



최대 힙에서 삭제 원리를 한번 알아보자.


힙에서 삭제는 트리의 root 노드만 삭제 및 조회가 가능하다.

(여기서 왜? 라고 물으면 안된다. 그러기 위해 힙이라는 자료구조를 만들었고 힙을 이용하여 O(lgN)에 최대 혹은 최소를 찾을 수 있기 때문이다.)


30을 삭제 해보자.



그리고 최대 힙에서 가장 마지막에 있던 값을 root 노드로 옮겨보자.


그렇다면 12가 1번 인덱스(root)로 갈 것이다.



12가 root인 subtree에서 최대 힙 특성을 만족하고 있는가?


못하고 있다. 따라서 우리는 12를 자식과 비교하면서 최대 힙의 특성을 지키도록 해주어야 한다.


12의 자식을 보니 왼쪽은 20, 오른쪽은14가 있다.


두 자식중 더 큰 값을 우리는 선택할 것이다.


따라서 20을 선택하게 되고 20과 12를 서로 교환해준다.



다시 12가 root인 subtree를 보자.


분명 왼쪽 자식인 8보다는 12가 크지만, 오른쪽 자식인 15보다는 12가 작다.


따라서 우리는 12와 15를 swap해주어야 한다.



이제 12를 root로하는 subtree를 보면 최대 힙을 잘 만족하고 있다.


이로써 삭제 과정을 마칠 수 있다.




한번 더 삭제를 해보자.


20을 삭제하고 힙에서 마지막에 있는 10을 root로 옮기면 다음과 같아진다.



10을 root로 하는 subtree에서 최대 힙 특성을 만족하지 못하고 있다.


따라서 우리는 10의 왼쪽 자식(15)과 오른쪽 자식(14)중 큰 값을 선택하게 될 것이고


그중 더 큰 값인 15와 10을 swap해줄 것이다.



이다음은 당연히 10과 12가 swap되어야 한다.


그 이유는 위와 계속해서 동일하다.

(10을 root로 하는 subtree가 최대 힙 특성을 만족하지 못하므로 왼쪽 자식인 8은 이미 10보다 작으니 상관없고 오른쪽 자식은 12이면서 10보다 큰 값이니 서로 swap해준다.)




이렇게 삭제 과정을 모두 마치게 되면 최대 힙은 아래와 같이 구성되게 된다.






4. 최대 힙 / 최소 힙 구현



최대 힙에서 삽입 / 삭제 과정을 이해 할 수 있었으니 이제 최대 힙을 코딩해보자.


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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <iostream>
#include <cstdio>
 
using namespace std;
 
template <typename T>
class HEAP {
private:
    int _sz;
    T *heapArr;
 
    int max(int a, int b) {
        return a > b ? a : b;
    }
 
    void push_swap(int cur) {
        if (cur == 1)
            return;
 
        int par = cur / 2;
        if (heapArr[par] < heapArr[cur])
        {
            T tmp = heapArr[par];
            heapArr[par] = heapArr[cur];
            heapArr[cur] = tmp;
 
            push_swap(cur / 2);
        }
    }
 
    void pop_swap(int cur) {
        int left, right, child;
 
        left = (cur * <= _sz ? cur * -1);
        right = (cur * + <= _sz ? cur * + -1);
 
        if (left == -&& right == -1)
            child = -1;
        else if (left != -&& right == -1)
            child = left;
        else
            child = (heapArr[left] > heapArr[right] ? left : right);
 
        if (child == -1)
            return;
 
        if (heapArr[child] > heapArr[cur])
        {
            T tmp = heapArr[child];
            heapArr[child] = heapArr[cur];
            heapArr[cur] = tmp;
 
            pop_swap(child);
        }
    }
public:
    HEAP(int n) {
        _sz = 0;
        heapArr = new int[n + 1];
    }
    ~HEAP() {
        delete[] heapArr;
    }
 
    int empty() {
        return !_sz;
    }
    int size() {
        return _sz;
    }
    T top() {
        return !_sz ? -: heapArr[1];
    }
 
    void push(int val) {
        heapArr[++_sz] = val;
        push_swap(_sz);
    }
 
    void pop() {
        if (!_sz)
            return;
 
        heapArr[1= heapArr[_sz--];
        pop_swap(1);
    }
};
 
int main()
{
    int size;
    cin >> size;
    HEAP<int> pq(size);
 
    int arr[] = { 2,4,11,12,8,10,14,12,20 };
    for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
        pq.push(arr[i]);
 
    pq.push(30);
    pq.push(15);
 
    pq.pop();
    pq.pop();
 
    cout << "최종적으로 maxheap에서의 root 값 :: " << pq.top() << endl;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





삽입 과정인 push 부분


1
2
3
4
5
6
7
    void push(int val) {
        heapArr[++_sz] = val;
        push_swap(_sz);
    }
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


push를 할 때는 위에서 언급했듯이 항상 힙의 마지막 부분에 삽입을 한다.


그 말은 즉슨 힙의 크기 다음을 나타내는(_sz + 1)부분에 넣는다는 의미이다.


위 그림에서 현재 힙의 크기는 9이다.(노드 9개)


이때 push를 하게되면 10번 인덱스에 값을 추가하면 되니 ++_sz와 동일하다는 의미이다.


이제 push를 한 후 push_swap(_sz)에 들어가게 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    void push_swap(int cur) {
        if (cur == 1)
            return;
 
        int par = cur / 2;
        if (heapArr[par] < heapArr[cur])
        {
            T tmp = heapArr[par];
            heapArr[par] = heapArr[cur];
            heapArr[cur] = tmp;
 
            push_swap(cur / 2);
        }
    }
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


위 코드는 최대 힙을 만족하도록 하기위해 하는 과정이고 앞서 삽입 과정에서 설명해주었다.


k번째 노드의 자식이 k * 2, k * 2 + 1임을 이전에 말했다.


그렇다면 k * 2와 k * 2 + 1의 부모는 k이다.


부모는 /2로 확인이 가능하며 (k * 2) / 2 그리고 (k * 2 + 1) / 2로 나타낼 수 있다.


위의 그림에서 인덱스 8번과 9번의 부모는 8/2 = 4, 9/2 = 4 즉, 4이다.



삽입 과정에서는 자신이 부모보다 더 큰값을 가진다면 두 값을 swap하게 된다.


swap을 하게 됐으니 이전에 자식은 부모위치로 가게 되었을 것이고, 이때 재귀 함수를 통해 최대 힙을 만족하도록 반복해준다.



즉, 아래그림처럼 30을 삽입하였고 30의 인덱스는 10이며 부모는 10/2인 5번 인덱스이다.


30과 10을 보았을 때 자식인 30이 더 크므로 swap을 하고 재귀를 통해 이번에는 5번인덱스부터 보게 된다는 것이다.


5번 인덱스에는 30이 들어있게 되고 5번 인덱스의 부모는 5/2인 2번 인덱스니 서로 또 비교하고 swap을 해주게 된다는 의미이다.





삭제 과정인 pop부분


1
2
3
4
5
6
7
8
9
10
    void pop() {
        if (!_sz)
            return;
 
        heapArr[1= heapArr[_sz--];
        pop_swap(1);
    }
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


pop 함수를 통해 삭제를 하게 해준다.


이때 첫번째 if(!_sz) return;의 의미는힙의 크기가 0이면 pop할게 없으니 return해준다는 의미이다.


앞서 삭제 원리를 알려줬듯이 힙의 root를 우선 삭제해주고 힙의 마지막에 위치한 값을 root에 넣어주는 코드이다.


그 말이 즉 heapArr[1] = heapArr[_sz--];와 동일하다.



그 후 pop_swap 함수에 들어가게 된다.


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
    void pop_swap(int cur) {
        int left, right, child;
 
        left = (cur * <= _sz ? cur * -1);
        right = (cur * + <= _sz ? cur * + -1);
 
        if (left == -&& right == -1)
            child = -1;
        else if (left != -&& right == -1)
            child = left;
        else
            child = (heapArr[left] > heapArr[right] ? left : right);
 
        if (child == -1)
            return;
 
        if (heapArr[child] > heapArr[cur])
        {
            T tmp = heapArr[child];
            heapArr[child] = heapArr[cur];
            heapArr[cur] = tmp;
 
            pop_swap(child);
        }
    }
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus



pop_swap에서 left는 왼쪽 자식, right는 오른쪽 자식을 의미하게 되고


만약 왼쪽 자식이 존재한다면 cur * 2가 힙의 크기보다 작거나 같아야 한다.


즉, 아래 그림에서 1번 인덱스의 왼쪽 자식은 2번 인덱스이고 힙의 크기가 현재 9이기에 2번 자식은 존재한다.


하지만 5번 인덱스의 왼쪽 자식은 10번 인덱스인데 힙의 크기가 9이므로 5번의 왼쪽 자식은 존재하지 않는다는 의미이다.


그렇게 left와 right를 구해주고 자식이 없다면 -1이라는 값을 가지도록 하게 한다.


1
2
3
4
5
6
7
8
9
        if (left == -&& right == -1)
            child = -1;
        else if (left != -&& right == -1)
            child = left;
        else
            child = (heapArr[left] > heapArr[right] ? left : right);
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


첫번째 if문은 왼쪽, 오른쪽 자식이 둘다 없다면 내가 최대 힙인지 판별할 child는 없다는 것이다.


위의 그림에선 5번, 6번, 7번 인덱스인 노드들같은 경우를 의미한다.


두번째 else if문은 왼쪽에만 자식이 있고 오른쪽에는 자식이 없는 경우이다.


이때는 child는 당연히 왼쪽 자식을 선택해야 한다.


세번째 else문은 왼쪽, 오른쪽 둘다 자식이 있는 경우이다.


이때는 왼쪽 자식의 값과 오른쪽 자식의 값 중 큰 값을 가진 인덱스를 선택하도록 한다.




** 왜 else if(left == -1 && right != -1)은 없나요 ?? **


왼쪽 자식이 없으면 당연히 오른쪽 자식은 없다.


이는 힙이 완전 이진 트리여서 자식이 항상 왼쪽에서 오른쪽순서로 채워지기 때문이다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
        if (child == -1)
            return;
 
        if (heapArr[child] > heapArr[cur])
        {
            T tmp = heapArr[child];
            heapArr[child] = heapArr[cur];
            heapArr[cur] = tmp;
 
            pop_swap(child);
        }
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


자식이 없다면 (child == -1) 이는 그냥 return을 하면 되고


자식이 있다면 자식의 인덱스가 가지는 값이 현재 인덱스의 값보다 크다면 서로 둘을 swap해주어야 한다는 의미이다.


아래 그림에서 pop을 하게 되면 1번 인덱스에서 출발하여 1번 인덱스의 값인 12와 1번 인덱스의 왼쪽 자식 값인 20을 swap해준다는 의미이다.


그리고 재귀를 통해 child로 내려가서 일어나는 현상은 아래 3번째 그림~4번째 그림과 같다.







5. Priority Queue



최대 힙, 최소 힙을 통해 우선순위 큐를 만들 수 있다.


이러한 우선순위 큐를 이용하여 Dijkstra Algorithm, Prim Algorithm 등등에 이용 할 수 있다.


우선순위 큐를 이용해보기 위해서는 #include <queue>에 있는 priority_queue를 사용해보자.





6. 힙 관련문제





반응형

'Applied > 자료구조' 카테고리의 다른 글

정적 할당을 이용한 Trie  (2) 2019.03.29
재귀가 아닌 반복문을 이용한 Trie  (0) 2018.03.07
[STL] deque 구현  (2) 2018.02.28
[STL] list 구현  (2) 2018.02.28
[STL] Pair 구현  (0) 2018.01.26