힙 Heap 이란

Heap 의 정의는 특정한 규칙을 만족하도록 구성된 이진트리 이다.

여기서 특정한 규칙은 부모노드가 자식노드 이상의 값을 가지고 마지막레벨(깊이)를 제외한 모든 레벨은 꽉차 있어야 하고 마지막레벨 은 왼쪽부터 순서대로 채운다. 라는 조건이다.

( 이때 부모 자식관계에서 부모노드가 자식노드 이상의 값을 가진다 라는 조건을 힙의 대소관계 라고한다 )

끝

이것만 만족하면 된다.  여기서 눈여겨 볼것은 부모노드가 자식노드 이상의 값을 가진다 라는데 이것은 부모와 자식 둘만 서로 보면 되기 때문에 상당히 만족하기 쉬운 조건이다. 이런 힙을 어이다가 사용하는가 ?

최대 값을 가능한 빠르게 찾을 때 유리하다. 최대값 = 루트가 가진 값 이기 때문이다.

그 생긴새는 이런 식으로 생겼다. google 에 heap 이라 검색하고 이미지 를 찾아보면 굉장히 많이 나온다.

이 트리가 조건을 만족하는지 살펴보자

100 - 19 만족

100- 36 만족

19 - 17 만족

19 - 3 만족

17 - 2 만족

17 - 7 만족

36 - 25 만족

36 - 1 만족

자 부모노드와 자식노드 사이의 관계 힙의 대소관계는 만족한다. 그럼이제 모양이 알맞은지 확인하자

마지막 레벨 ( 가장 깊이가 깊은 부분 ) 은 왼쪽부터 차례대로 채운다. 만족

그 외의 레벨들은 모두 가득 차있어야 한다. 만족

모양적인 부분까지 문제없이 만족하고 있으니, 이 트리는 힙 이다 ! 

자 이런 힙을 어떻게 구현해야할까 ? 물론 struct 로 직접 이진 트리를 구현해서 하는 방법이 있기야 하지만 더 쉬운 방법이있다. 바로 우리가 흔히 사용하는 배열을 이용하는 방법이다.

어떻게 배열로 트리를 구현할수 있을까? 생각보다 간단하다

배열의 인덱스만 확인을 하면 자신의 왼쪽자식, 오른쪽 자식, 부모를 찾을수 있기 때문이다.

' 앵? 그래 그렇다 치자 그런데 어떻게? ' 라고 생각할수있다.

우선 힙의 생김새를 생각해보자, 마지막 한줄을 빼고는 모두 꽉차 있어야 한다. 그럼 배열의 인덱스를 이렇게 준다고 생각해보자

1

    2                       3

   4             5          6           7

   8    9        10  11   12  13     14  15

이제 위의 힙을 배열에 넣는 다고 생각을 하면

0	1	2	3	4	5	6	7	8	9
-	100	19	36	17	3	25	1	2	7

10	11	12	13	14	15	16	17	18	19
-	-	-	-	-	-	-	-	-	-

이런식으로 표현이 될것이다. 규칙을 한번 찾아보자

100 < 1 > 의 왼쪽 자식은 19 < 2 >  이고 오른쪽 자식은 36  < 3 > 이다. 

19 < 2 > 의 왼쪽자식은 17 < 4 > 이고 오른쪽 자식은 3 < 5 > 이다.

36 < 3 > 의 왼쪽 자식은 25 < 6 > 이고 오른쪽 자식은 1 < 7 > 이다.

규칙이 조금 눈에 들어오는가? 자신의 인덱스에 2를 곱했더니 왼쪽자식이 2를 곱한값에 1 을 더했더니 오른쪽 자식이나왔다.

반대로 자신을 2로 나눈 몫( 인덱스 )이 부모를 가리키고 있다.

식으로 정리해보면

자신의 인덱스를 i 라고 했을 때

자신의 부모 = i / 2

자신의 왼쪽 자식 = i X 2

자신의 오른쪽 자식 = i X 2 + 1

이런식으로 찾아가면 자신의 부모를 찾을수 있다.

자 그럼이제 힙에서 삽입은 어떻게 해야할까?

가장 먼저 생각할수있는 것은, 루트에서 부터 대소를 비교해가며 자신이 어디있는지 찾아가는 방법이 있을 수 있다.

하지만 이방법을 사용하면 큰 문제가 생길수 있다.

모양이 망가질수가 있기 때문이다. 

그래서 거꾸로 생각을 해서 올라가면 쉽다.

먼저 모양을 만들고 나서 생각을 해보는 것이다.

우린 힙을 만들때 다음에 원소가 올 위치를 알수있다. 위의 힙을 예로 들면 이제 3의 왼쪽 자식 부분에 새로운 노드가 달릴 것이다.

그럼 어떤 숫자가 올지는 모르지만 그 숫자를 일단 그곳에 매달아 둔다. 예를 들어 20 이라는 숫자를 넣는다고 생각해보자.

조잡하다....

우린 이 그림을 보면서 어느 곳이 잘못 됬는지를 찾아볼수 있다. 그림실력?

바로 3과 20의 대소관계가 잘못 되있는 것을 알수있다. 그럼 이제 어떻게 해야하는가? 간단하다 둘의 위치를 바꾼다 ! 

자 우린 아직도 19 와 20의 대소관계가 잘못되어있음을 발견할수 있다. 다시 바꿔준다.

이제 우리는 이 힙에서 잘못된 점을 찾을수 없고 무사히 노드 하나가 추가된 것을 확인 할 수 있다.

이 과정을 UP_Heap 이라고 하기도 하고, Push_Heap 이라고 하기도하고 중요하지않다 적어도 어떻게 집어 넣어야 하는가 그 과정을 알고 있으면 된다.

보다시피 어마어마하게 많은 노드가 들어있다 한들 비교과정이 그렇게 많이 필요하지 않다는 것을 우리는 알수 있다.

실제로도 이 삽입과정은 O( lg N ) 의 수행시간을 가지기 때문에 굉장히 빠른편이다.

자 그럼 삽입을 해봤으니 이젠 삭제를 해봐야할 차례이다. 우리는 위의 새로 만들어진 노드가 추가된 이 표에서 무엇이 삭제 되어야 하는지 알 수 있다. 

3이 삭제 되어야한다고 생각한다면 당신은 속았다. 

힙이 만들어진 이유를 생각해보자,최대값을 빠르게 찾기 위해 만들어진 것이 Heap 구조이다. 

그렇다는건 루트 부분이 삭제가 되어야 한다는 뜻인데, 루트가 사라지면 트리가 두개로 나눠져버리고 마는데 어떻게 해야하지 라는생각이 자연스럽게 들것이다. 그렇죠?

삽입을 했던 과정을 거꾸로 해본다고 생각을 하자 모양을 만족하되 노드를 하나 줄일려고 하면 지워줘야 할 부분이 어디인지 알수 있다 바로 3 이다. 3이 사라져도 힙의 구조는 유지되기 때문이다. 

자 그럼 일단 3을 지우자, 그리고 이 지워진 3의 값을 루트에다 덮어 씌워보자

자 일단 지워졋어야할 100이 지워졌다 ! 하지만 지금 이 트리는 힙이 아니다. 

모양은 맞지만 대소관계에서 잘못된 부분이 있기 때문이다.

대소관계를 만족시키기 위해 3을 봤더니 어라? 3은 20보다도 작고 36보다도 작다 뭐랑 자리를 바꿔야 할까 ?

힙의 정의에 대해 다시한번 생각해보자 루트에 오는 것은 가장 큰 녀석이다. 그렇다면 36과 바꿔줘야 할것이다.

감이 슬슬 오는가 ? 이제 우린 딱 보고 ' 아 이젠 3이랑 25랑 자리를 바꾸면 되겠네 ' 라고 생각을 할수 있다. 

할수있겠죠? 어때요 참 쉽죠

자 삭제과정이 완료 되었다. 보라, 100의 값을가지고 있던 기존의 루트는 사라졌으며, 힙의 구조도 만족하고있고 대소관계도 만족하고 있는 나무랄데 없는 힙이다.

지금 삭제를 했던 일련의 과정을 Down_Heap 혹은 Pop_Heap 이라고 하는데 과정을 안다는 것이 중요하다.

마찬가지로 이 삭제과정도 아무리 많은 원소가 있든 생각보다 많은 비교과정이 필요없다는 것을 알수있다.

이 삭제과정 또한 시간복잡도 O ( lg N ) 을 가지는 아주 훌륭한 녀석이다. 

자 이러한 힙을 사용한 것으로는 대표적으로 Heap_Sort 가 있다. 자세한 알고리즘은 구글링을 하시도록 하고,

이 Heap 을 사용하여 만든 sorting 으로 최 악 의경우에도 O (lg N ) 을 보장하는 아주 뛰어난 Sorting 이다.

힙에 대한 이야기는 여기서 이만 마치겠다.