힙(Heap) 자료구조

힙은 우선순위 큐가 이용하는 자료구조가 된다.

힙이란?

최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리의 형태로 만들어진 자료구조

이말을 뜯어서 말하자면 

1. 완전 이진 트리 형태
2. 빠르게 찾기
3. 최댓값 or 최솟값

이 3가지가 충족해야 힙 상태가 만들어진다는것이다.

그럼 완전 이진 트리 부터알아보자

1. 완전 이진트리

이와 같은 구성을 트리 구조라고 부르고 최종 자식노드들을 제외한 각 노드(동그라미)들이 자식을 2개씩(이진) 가지고 있는 것을 완전 이진트리 라고 한다.

 

완전 이진트리는 약간의 조건이 있다

1. 마지막을 제외한 모든 노드들이 채워져 있어야 한다

2. 모든 노드들은 왼쪽부터 채워져가야 한다.'

 

이런식으로 힙은 완전 이진 트리가 되어있는것을 기본으로 한다. 구현을 할 때에도 이 이미지를 생각하고 있어야한다.

 

2. 빠르게 찾기

굉장히 기초적인 말이 될 수 있다. 우리가 정렬하는 이유는 우리가 원하는 숫자를 그만큼 빨리 가져오길 원하고 그것을 찾기 편하게 하려고 하는것이다. 그런면에선 당연한 말이 될 수 있다. 

그렇다면 힙에서의 빠르게찾기란 우리가 원하는 기준으로 완전 이진 트리가 구성이 되는것을 말할수 있다.

여기서 우리가 원하는 기준이 바로 최댓값과 최솟값의 연관이 있다.

 

2. 최솟값과 최댓값

우리가 힙을 사용한다면 최댓값과 최솟값을 빠르게 찾고 뽑아내려고 사용하는 상황이 될 것이다. 그게 우리가 원하는 기준이고 힙 상태를 만들때의 기준이 될 것이다.

min heap(최소 힙) - 루트 노드가 가장 작은 것
부모 노드의 값 <= 자식 노드의 값
max heap(최대 힙) - 루트 노드가 가장 높은 것
부모 노드의 값 >= 자식 노드의 값

여기서 우리는 조건을 하나 세워줘야한다.

부모 노드는 항상 자식 노드보다 우선순위가 높다.

우리는 이러한 작은 조건을 하나 내면서 최솟값과 최댓값을 구하기 위해 완전 이진트리를 사용 할 것이고 누가 더 우선적으로 가야하는가에 따라 우리가 원하는 결과를 얻어낼수있는 장담을 얻어낸것이다.

이게 기준이 된다 그렇다면 우리가 힙 자료구조에 대한 말을 다시 보자

최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리의 형태로 만들어진 자료구조

"완전 이진 트리형태로 만들어서 노드들의 관계가 최댓값 기준 혹은 최솟값 기준으로 이루어져
우리가 원하는 작거나 큰 수를 빠르게 찾아 낼수 있는 구조" 라고 할 수있는것이다.

 

구현

우리는 사람들이 정렬하면 가장 많이 떠올리는 오름차순을 예로 들어 공부해 볼 것이다.

당연히 배열로 예를 들어 볼 것이고 그림으로 표현해 보면서 이해력을 높여 보자

 

	3	10	35	23	19	47	60	35	80	44
0	1	2	3	4	5	6	7	8	9	10	11

인덱스의 숫자와 부모의 숫자를 보면 특이한 성질이 나타난다

1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스  X 2
2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 X 2 + 1
3. 부모 노드 인덱스 = 자식 노드 인덱스 / 2

이 법칙은 절대로 깨지지 않는다. 예를 들어 index2인 노드의 왼쪽자식노드를 찾고 싶으면 X2인 index4가 되는 것이다.

그럼 이 법칙을 이용하여 우리는 최댓값 혹은 최솟값을 빠르게 찾을수 있도록 설정을 해보자

 

 

우리에게 익숙한 배열을 표현 한 완전 이진 트리이다. 

힙 상태로 만들어 보자

1. 7과 8을 비교 후 더 큰 수를 부모노드(자식노드 / 2)인 수와 비교하여 더 작다면 교환
2. 5와 6을 비교후 더 큰 수를 부모 노드(자식 노드 / 2)와 비교하여 더 작다면 교환
3. 교환 후 3과 4와 비교 후 더 큰 수를 부모 노드(자식노드 / 2)와 비교하여 더 작다면 교환
4. 교환된 1과 교환 된 2를 비교 후 더 작은 수를 루트 노드와 비교후 교환

 

 

                       완성 후

이런식으로 만들어 진것이 MIN_HEAP이다. 

( 이것을 반대로 하면 MAX_HEAP이다. )

 

언뜻 정렬이 된 것처럼 보이겠지만 아니다 그저 최솟값을 가장 위의 노드로 올렸을뿐 정렬이 된 것은 아니다.

 

여기서 자식노드의 이야기가 빠질수없다.

우리는 최솟값과 최댓값을 빠르게 찾기 위한 상태를 만들어주고있는 과정이다.

힙 자료구조는 가장 높은 노드에 최솟값이 오게하거나 최댓값을 오게하는데 의의를 둔다 정렬에 관한건 이후 힙 정렬에 다룰것이다

 

 

 

이런식을 힙 자료구조 라고 한다. 

꼭 다시 복기해야한다. 자료구조와 정렬은 엄연히 다른것이다. 그것을 명심해야한다.

힙 이라는 자료구조를 생각한다면 이런식으로 만들어준다 라고 생각해야한다.

정렬은 그 이후의 일이다