[ 자료구조 힙 ] 개념과 구현방법 (C++)

이번 글에서는 자료구조 '힙 에 대해서 이야기해보고자 한다.

1. 힙 (Heap) ??

자료구조 힙이 무엇인지에 대해서 부터 이야기해보자.

힙은 주어진 데이터들 중에서 특정 기준에 부합하는 '최댓값' 혹은 '최솟값'을 빠르게 찾아낼 수 있는 자료구조이다.

힙은 '완전이진트리(Complete Binary Tree)'를 기반으로 한 자료구조이다. 완전이진트리에 대해서 정말 간략하게만 설명을

하자면, '이진트리' 즉, 하나의 부모당 자식이 최대 2개까지만 존재하는 트리 중에서 왼쪽부터 차례대로 삽입된 형태를 가진

트리를 완전이진트리 라고 한다.

간단하게 예시를 몇 개만 들자면 다음과 같다.

위의 그림을 왼쪽부터 1, 2, 3 번이라고 번호를 붙여보면, 1, 2번은 완전이진트리, 3번은 완전이진트리가 아니다.

왜냐하면 3번 같은 경우, 가장 마지막 노드가 왼쪽이 아닌 오른쪽에 삽입된 형태이기 때문에 이는 완전이진트리가 아니다.

다시 본론으로 돌아와서, 힙은 완전이진트리를 기반으로 한 자료구조이다.

힙에서는 부모노드와 자식노드 사이의 관계가 하나 존재한다. 바로, 부모노드의 값은 무조건 자식노드의 값보다 크거나,

부모노드의 값은 무조건 자식노드의 값보다 작다는 관계이다.

부모노드의 값이 자식노드의 값보다 큰 관계일 때를 "최대힙" , 부모노드의 값이 자식노드의 값보다 작은 관계일 때를

"최소힙" 이라고 한다.

힙에서 '형제노드'간의 관계는 존재하지 않는다. 오로지 '부모노드와 자식노드만을 비교' 하게된다.

즉, '최대힙'이라고 가정했을 때, 트리의 가장 꼭대기 층에 있는 루트노드의 값이 트리에 존재하는 값들 중 가장 큰 값이 될 것이다.

우리가 특정 기준에 부합하는 최댓값을 찾고 싶다고 한다면, 힙을 구현 후, 가장 루트의 값을 가져오면 되는 것이다.

하지만, 단순히 그냥 가져올 수는 없고 또 다른 과정을 진행해주어야 한다.

이 과정들은 밑에서 천천히 알아보자.

2. 힙의 작동원리

지금부터는 '최대힙'을 기준으로 설명을 하겠다. 즉, 부모노드의 값이 자식노드의 값보다 크게 오도록 설정하는 과정으로

설명을 하겠다.

다음의 데이터들을 가지고 최대힙에 대해서 알아보자.

[ 41 67 34 0 69 78 62 64 ] 이렇게 8개 짜리 배열이 있고, 이 8개를 힙에 삽입해보자.

삽입의 과정은 다음과 같다.

1. 트리의 가장 마지막 노드 다음에 현재 삽입하고자 하는 데이터를 넣어준다.

2. 부모노드와 비교하면서 부모노드보다 더 큰 값이라면 부모노드와 Swap해준다.

3. 2번 조건을 만족하지 않을 때 까지 혹은 루트 노드가 아닐 때 까지 반복한다.

위의 과정을 그림으로 알아보자.

가장 먼저 '41' 이 들어올 것이다. 현재 힙에는 아무런 데이터도 존재하지 않는다.

가장 처음에 들어온 데이터 이기 때문에 저렇게 첫 번째 노드가 생성될 것이다.

2번과정 3번과정은 당연히 진행되지 않을 것이다. 왜냐하면 비교할 부모노드가 존재하지 않기 때문이다.

두 번째로 '67'이 들어올 것이다. 현재 힙은 위와 같은 상태로 존재한다. 이제 순서대로 진행해보자.

1. 트리의 가장 마지막 노드 다음에 삽입한다.

현재 트리의 가장 마지막 노드는 '41'이 존재하는 '1'번 노드일 것이다. 그럼 1번 다음 노드인, '2'번 노드에 삽입해보자.

2. 부모노드와 비교하면서 부모노드보다 더 큰 값이라면 부모노드와 Swap 해준다.

부모노드와 비교를 해보니, 67 > 41 로, 부모노드보다 더 큰 값이다. 그럼 부모노드와 Swap을 해주자.

3. 2번 조건을 만족하지 않을 때 까지 혹은 루트 노드가 아닐 때 까지 반복한다

다시 한번 부모노드와 비교를 해보려고 하니, 루트노드까지 와버려서 부모가 없다. 그럼 반복을 중단한다.

세 번째로 '34'를 삽입해보자. 트리의 가장 마지막 노드 다음 노드이니, 현재 가장 마지막 노드는 '2'번 노드이고, 그 다음 노드인 '3'번 노드에 삽입해보자.

부모노드와 비교를 해보니, 부모노드보다 더 작은 값이다. 즉, 최대힙의 규칙에 어긋나지 않는다. 따라서, 반복을 중단한다.

네 번째로 0을 삽입해보자.

이렇게 되고, 더 이상의 변화는 없다는 것을 이제는 쉽게 알아차릴 것이다.

다섯 번째 값인 '69'를 삽입해보자.

마지막 노드의 다음 노드에 삽입한다면 위의 그림과 같이 '69'가 들어갈 것이다.

2. 부모노드와 비교하면서 부모노드보다 더 큰 값이라면 부모노드와 Swap 해준다.

부모노드인 '41'과 비교해보니, 더 큰 값이므로 부모노드와 Swap을 해주자.

또 다시 한번, 부모노드와 비교를 해보니 69 > 67로 또 더 큰 값이다. 그럼 또 Swap을 해주자.

또 비교를 하려고 보니, 루트노드라서 부모가 존재하지 않는다. 반복을 중단한다.

여섯번째 값인 '78'을 삽입해보자.

부모노드와 비교해서 더 크므로 Swap, 그 이후에 한번 더 비교해서 Swap을 하면 다음과 같이 될 것이다.

일곱번째 값인 '62'를 삽입하면, 부모노드인 '69'와 비교했을 때 더 작기 때문에 아무런 Swap이 일어나지 않을 것이다.

즉, 다음과 같이 될 것이다.

마지막 값인 '64'를 삽입해보자.

부모노드와 비교를 해보니 64 > 0 이므로 Swap이 일어난다.

더 이상의 Swap은 일어나지 않는다.

위의 과정이 힙에 삽입하는 과정이다. 모든 데이터들을 다 삽입하고 나니 루트 노드에는 가장 최댓값이 들어가있음을

확인할 수 있다.

이제 우리는 저 값을 사용하면 된다. 그런데 ! 한 가지 상황을 더 추가적으로 생각해보자.

"위의 8개의 데이터를 가장 큰 값들 순서대로 하나씩 가져와야 하는 상황" 이라고 생각해보자. 간단하게 생각해서 내림차순으로

값을 하나씩 가져와야 하는 상황이다 라고 생각하자.

그럼 방법이 하나 있다. '78'을 가져오고, '78'을 없애버린 후에 다시 힙을 만들어버리면 되잖아?

하지만 '78'을 위의 상태에서 없애버릴 수는 없다. 왜냐하면 "트리에서 루트노드가 없어진다는 것은, 트리의 구조가 완전히

깨진다는 것을 의미" 하기 때문이다. 따라서 위의 형태를 그대로 유지하면서 값을 가져와야 한다.

지금부터 위의 문제들을 해결하기 위해서 어떻게 해야될지, '힙의 삭제 과정' 에 대해서 알아보자.

힙의 삭제 과정은 다음과 같다.

1. 우리가 가져올 '최대값'을 미리 저장해준다.

2. 가장 마지막 노드의 값과 루트 노드의 값을 Swap 해준다.

3. 현재 노드에서 자식 노드와 비교 하면서 더 작은 값이라면 Swap해준다.

4. 위치를 찾을 때 까지 3번 과정을 반복한다.

5. 미리 저장해둔 최댓값을 return 시켜주고, 힙의 크기를 1 감소시켜준다.

위의 상황을 그대로 가져와서 이제 삭제하는 과정을 알아보자.

우리가 위에서 8개의 데이터를 최대힙으로 삽입한 상태이다.

이제 최댓값을 하나씩 가져오는 '삭제'과정을 한번 진행해보자.

1. 우리가 가져올 '최대값'을 미리 저장해준다.

편의를 위해서, 'Result' 라는 곳에 저장을 해준다고 생각하자. 현재, Result = 78 이다.

2. 가장 마지막 노드의 값과 루트 노드의 값을 Swap 해준다.

Swap을 해주자. 다시 한번 말하지만, Swap을 해주는 이유는, 단순히 78을 그대로 가져와 버리면, 루트노드가 사라지게 되는

꼴이 되어버리고, 이는 트리의 구조를 완전히 깨버리기 때문에 그대로 가져올 수가 없기 때문이다.

Swap을 하게 되면 이렇게 될 것이다. 그런데 Swap을 해주니까, 우리가 공들여 만들어놨던 '최대힙'의 규칙이 깨진 모습을

확인할 수 있다. 따라서, 다시 '최대힙'의 규칙을 유지할 수 있도록 루트 노드의 있는 값을 위치에 맞게 만들어 줘야 한다.

3. 현재 노드에서 자식 노드와 비교 하면서 더 작은 값이라면 Swap해준다.

현재 노드는 '1번' 노드이다. 자식 노드와 비교를 해봐야 하는데, 자식이 2개가 있다. 무슨 자식과 비교를 해야할까 ??

위에서도 말했듯이, 힙에서 형제노드 간에 관계는 없다. 즉, 왼쪽자식, 오른쪽자식 중 무슨 값이 더 큰지 더 작은지에 대해서

정해진 건 없다. 따라서, 왼쪽 자식과 오른쪽 자식을 비교해서 더 큰 값을 가진 자식을 찾아서 비교해 주면 된다.

간단한 예시로 아래의 상황을 생각해보자.

이런 상황에서 '50' 과 , [ 65 , 70 ] 둘 중 하나를 선택해서 Swap을 해줘야 하는데, 형제 간의 대수를 따지지 않고

단순히, '65'과 Swap 한다고 생각하면,

위와 같은 형태가 될 것이고, 이는 역시 최대힙에 부합하지 않는 형태가 될 수 있기 때문이다.

즉, 현재 노드에서 자식노드와 비교를 해줘야 하는데, 이 전에 먼저 '2개의 자식들 중에서 더 큰 값 찾기' 를 진행해 주어야

한다. 다시 본론으로 돌아오자.

이 상태에서, 2개의 자식을 비교해보자. '69'가 더 큰 값이다. 그럼 0과 69를 비교하는 것이다.

0이 더 작은 값이기 때문에 Swap 해준다.

Swap을 하는 순간, '현재노드'가 다음과 같이 한 칸 아래로 내려왔다.

4번 과정이 3번 과정을 반복하는 것이므로 또 진행해보자.

자식 2개를 비교해보니, 62 > 34 이므로, 0과 62를 비교해보면 62 > 0 이므로 또 Swap을 해주자.

또 한번 비교해 보려고 하니, 더 이상의 자식노드가 존재하지 않는다.

즉, 위치를 찾았다는 것을 의미한다.

5. 미리 저장해둔 최댓값을 return 시켜주고, 힙의 크기를 1 감소시켜준다.

이제 미리 저장해둔 Result 값인 '78'을 return 시켜주고, 힙의 크기를 1 감소시켜주자.

힙의 크기를 1 감소시켜준다는 것을 그림으로 표현하면 다음과 같이 표현할 수 있다.

'78'이 원래 가장 마지막 노드에 존재했었지만, 어차피 '78'은 이제 떠난 값이고 그에 맞춰서 크기도 1 감소시켰으니

위와 같은 형태가 남았다고 생각할 수 있다.

모든 값을 삭제하는 과정을 보이기엔 너무 과정이 많으니, 지금 현재 최대값인 '69'를 삭제하는 과정만 한번 더 진행해보자.

1. 우리가 가져올 '최대값'을 미리 저장해준다.

Result = 69 이다.

2. 가장 마지막 노드의 값과 루트 노드의 값을 Swap 해준다.

Swap해주게 되면 다음과 같이 트리가 존재하게 된다.

3. 현재 노드에서 자식 노드와 비교 하면서 더 작은 값이라면 Swap해준다.

자식 노드와 비교하기전, 자식노드들 끼리 비교를 해보자. 67 > 62 이므로, 0과 67을 비교해주자.

67 > 0 이므로, Swap 해주자.

그렇게 되면 위의 형태처럼 존재하게 될 것이다.

4. 위치를 찾을 때 까지 3번 과정을 반복한다.

위의 과정을 한번 더 반복하면 다음과 같이 존재하게 될 것이다.

더 이상 비교할 자식 노드가 없다. 즉, 위치를 찾았다는 것을 의미한다.

이제 반복을 중단하자.

5. 미리 저장해둔 최댓값을 return 시켜주고, 힙의 크기를 1 감소시켜준다.

미리 저장해둔 '69'를 return 시켜주고, 힙의 크기를 1 감소시켜주면 다음과 같은 형태만 남았다고 생각할 수 있다.

위와 같이 힙의 삭제 연산을 진행할 수 있다.

3. 힙 구현하기

이제 힙을 직접 구현해보자. 코드로 직접 구현하기전에 몇 가지만 알아보고 들어가자.

실제로 힙을 구현할 때, 완전이진트리를 구현할 필요는 없다. 단순히 배열로도 구현할 수가 있다.

그런데 ! 우리는 배열로 구현할 것인데, 완전이진트리의 성질을 그대로 가져와서 구현할 것이다.

그럼 무슨성질이 있을까 ??

부모노드와 자식노드의 노드번호의 관계를 한번 보자.

예를 들어서 루트노드부터 번호를 매긴다면 아래와 같이 생각할 수 있다.

이렇게 노드번호를 매길 수 있다. 그럼 우리는 여기서 부모노드와 자식노드의 관계를 하나 알 수 있다.

"부모노드의 번호는 자식노드의 번호 / 2 이다." 반대로, "자식노드의 번호는 부모노드의 번호 x 2 or x 2 + 1" 한 값이다.

우리는 위에서 삽입이든 삭제든, 부모노드와 자식노드를 비교하는 과정이 참 많았었다.

우리는 지금부터, 이 부모노드와 자식노드를 비교할 때, 위와 같이 / 2 하는 연산 혹은 x 2를 하는 연산으로 비교할 것이다.

그리고, 실제로 우리는 완전이진트리가 아닌 단순 배열로 구현할 것이라고 말을 했다.

그럼, 위의 노드의 번호들을 배열의 Index번호로 생각할 수가 있다.

1번 Index의 왼쪽자식의 Index번호는 2번, 오른쪽자식의 Index번호는 3번,

4번 Index의 부모노드의 Index번호는 2번, 5번 Index의 부모노드의 Index번호는 2번

이런식으로 위의 번호들을 배열의 Index로 사용할 것이다.

그러기 위해서 정말 중요하게 지켜줘야 할 것이 있다.

배열을 선언하게 단순히 가장 앞에서부터 값을 넣는다면 '0번 Index'부터 값이 들어가게 되는데,

0번 Index가 들어가는 순간, 위의 관계를 계산할 수가 없어진다. 따라서, 우리는 0번 Index는 버리고, 1번 Index부터 사용

할 것이다. 이제 코드로 구현하러 가보자.

삽입하는 과정을 다시 가져왔다.

1. 트리의 가장 마지막 노드 다음에 현재 삽입하고자 하는 데이터를 넣어준다.

2. 부모노드와 비교하면서 부모노드보다 더 큰 값이라면 부모노드와 Swap해준다.

3. 2번 조건을 만족하지 않을 때 까지 혹은 루트 노드가 아닐 때 까지 반복한다.

그리고 코드를 먼저 보고, 라인별로 어떤 역할을 하는지 알아보자.

void Heap_push(int Data)
{
    int Idx = ++Heap_Idx;
    Heap_Arr[Idx] = Data;
    while ((Idx != 1) && (Data > Heap_Arr[Idx / 2]))
    {
        Swap(Heap_Arr[Idx], Heap_Arr[Idx / 2]);
        Idx = Idx / 2;
    }
}

힙에 'Data'라는 값을 삽입하는 과정이다.

Heap_Arr[] 는 단순 int형 배열이다. 절대로 트리를 직접 구현하지 않았다. 이제 라인별로 무슨 역할을 하는지 알아보자.

line 3)

- Heap_Idx 라는 변수가 힙의 가장 마지막 인덱스를, 즉, 힙의 크기를 나타내고 있는 변수이다.

  초기 Heap_Idx의 값은 0이다.

  1번 과정을 진행하기 위해서, 즉, 가장 마지막 노드 다음에 데이터를 삽입해주기 위해서, Idx = ++Heap_Idx 로 만들어주었다.

line 4)

- 1번 과정에서 "데이터를 넣어준다" 에 해당하는 부분이다.

line 5 ~ 9)

- 2번 ~ 3번 과정을 나타내는 부분이다.

  먼저 3번 과정에서 제시한 조건을 살펴보면, "조건에 만족하지 않을 때 까지" or "루트 노드가 아닐 때 까지" 반복하라고

  했다.

  line 5) 에서 위의 조건문을 걸어준 것이다. Idx != 1 이라는 말은, "루트노드가 아니에요" 라는 것을 의미하고,

  Data > Heap_Arr[Idx / 2] 이 조건문은, 현재 데이터와, 현재 노드의 부모노드와( /2 연산) 비교해서 더 크다면,

  최대힙을 만들어주기 위해서 Swap을 해주는 것이다.

  line 8) 에서는 적절한 위치를 찾을 때 까지 계속 올라가 줘야 하므로, 노드의 위치를 Swap한 부모 노드의 위치로 바꿔준다.

그럼 이제 삭제하는 코드를 보자.

1. 우리가 가져올 '최대값'을 미리 저장해준다.

2. 가장 마지막 노드의 값과 루트 노드의 값을 Swap 해준다.

3. 현재 노드에서 자식 노드와 비교 하면서 더 작은 값이라면 Swap해준다.

4. 위치를 찾을 때 까지 3번 과정을 반복한다.

5. 미리 저장해둔 최댓값을 return 시켜주고, 힙의 크기를 1 감소시켜준다.

int Heap_pop()
{
    int Result = Heap_Arr[1];
    Heap_Arr[1] = Heap_Arr[Heap_Idx--];
    
    int Parent = 1;
    int Child;
    while (1)
    {
        Child = Parent * 2;
        if (Child + 1 <= Heap_Idx && Heap_Arr[Child] < Heap_Arr[Child + 1]) Child++;
        if (Child > Heap_Idx || Heap_Arr[Child] < Heap_Arr[Parent]) break;
        Swap(Heap_Arr[Child], Heap_Arr[Parent]);
        Parent = Child;
    }
    return Result;
}

line 3)

- 1번 과정이다. 우리가 가져올 값(최대값 or 최소값)은 '루트노드에 위치' 한다. 즉, 1번Index에 존재하는 값을 저장해

  주면된다.

line 4)

- 이게 사실 2번 과정을 나타낸 것인데, 말로 표현한것과 실제 코드와는 조금 다르다.

  말로는 가장 마지막 노드의 값을, 루트 노드의 값과 Swap을 해주라고 하였는데, 본인이 구현할 때는,

  단순히 가장 마지막 노드의 값을 루트 노드의 값에 복사를 해주었고, 말로는 5번과정에 진행한, "힙의 크기를 1 감소" 시키는

  과정을 위에서 바로 진행해 주었다. 그렇게 되면, 가장 마지막 노드는 사실상 없어진 것과 같은 효과로 삭제 연산을

  진행할 수 있다.

line 8 ~ 15)

- 3번 4번 과정을 진행한 것이다.

  'Parent' 변수의 초기값은 1번, 즉 루트노드를 의미하고 있다.

  'Child'노드는 초기에는 Parent의 * 2를 한 값, 즉, 왼쪽 자식노드를 의미하고 있다.

  그런데, 위에서도 말했듯이 자식노드와 비교하기 전에, 자식들 간의 대소관계를 비교해 주어야 한다고 했다.

  line 11) 에서 자식들 간의 대소관계를 비교하고 있는 것이다.

 Child + 1 <=  Heap_Idx → "현재 노드의 오른쪽 자식이 존재하고"

 Heap_Arr[Child] < Heap_Arr[Child + 1] → "왼쪽 자식보다 오른쪽 자식이 더 크다면" → Child++.

 만약 위의 조건에 부합되지 않는다면, Child는 왼쪽 자식노드를 가르키는 값으로 그대로 남아있을 것이다.

 line 12) 는 위치를 찾은 경우를 의미한다. 즉, 반복을 중단해야 할 조건문을 설정해놓은 것이다.

 Child > Heap_Idx → " 자식노드가 존재하지 않는다면 "

 Heap_Arr[Child] < Heap_Arr[Parent] → "부모가 이미 더 크므로, Swap을 할 필요가 없다면" → Break

 line 13) 에서는 위의 조건들을 모두 만족하는 상황이기 때문에 Swap을 해주는 과정이다.

 line 14) 에서는 계속된 탐색을 위해서 Parent의 값을 다시 갱신해 주는 과정이다.

본인은 힙의 삽입과 삭제 과정을 위와같이 구현해 보았다.

마지막으로 힙에 대한 약간의 설명만 더하고 글을 마치도록 하겠다.

4. 힙 ? 왜 빠를까 ??

우리는 지금까지 힙이 최대값이나 최소값을 찾을 때 빠르다. 그래서 삽입은 이렇게 하고 ~ 삭제는 저렇게 하고 ~

코드로는 이렇게 짠다 ~ 까지 알겠는데, 힙이 왜 빠른지에 대해서 생각해보자.

단순히, 순차탐색으로 최댓값 최솟값을 찾을 경우, N번 만큼의 탐색을 해주어야 한다. N 값이 커지면 커질수록 너무나도

많은 시간이 걸릴 수 밖에 없다.

하지만, 힙 같은 경우 삽입시 logN, 즉 트리의 높이만큼만 비교를 하게 된다. 따라서, 시간복잡도가 O(logN) 으로

N번만큼의 탐색을 하는 순차탐색에 비해서 더 빠른 것이다.

이렇게 빠른 점을 이용해서, '다익스트라 알고리즘' 혹은 '프림알고리즘' 같은 여러 알고리즘 들에서도 단순히 배열로만

구현하는 것이 아니라, 우선순위큐 (우선순위큐는 힙을 기반으로, 기준에 맞는 최소값 or 최댓값을 선출시킴) 를 이용한

방법으로 구현하기도 한다.

이를 이용한 '힙 정렬'도 존재한다. 혹여나 궁금하다면 아래의 링크를 타고 가면 볼 수 있다.

[ 힙 정렬 알아보기(Click) ]

마지막으로 ! 위에서도 말했듯이 지금 이글은 모든 설명이 '최대힙'으로 설명이 되어있다.

최소힙은, 최대힙과 반대로, 부모노드의 크기가 자식노드의 크기보다 작게 오도록 바꿔주기만 하면 된다.

실제 코드로 구현할 때에는 단순히 부등호 방향만 바꿔주면 된다.

모든 로직과 과정이 똑같으니 '최소힙'은 따로 설명하지 않겠다. 위의 글은 '최대힙'으로 설명이 되어있다 !!!