힙(Heap) 이란?

1. 힙(Heap)
   1-1. 힙이란?
   1-2. 힙의 종류
   1-3. 힙의 활용
   1-4. 예시(힙 삽입)

 

 

 

---

 

 

1. 힙(Heap)

1-1. 힙이란?

엉...엉덩이...?

 

맨 처음에 힙을 들었을 때 엉덩이(hip)가 생각날 수도 있지만

힙은 heap이다. 무언가를 차곡차곡 쌓아 올린 더미라는 뜻이다.

 

힙(Heap)은 완전이진트리의 형태로 만들어진 자료구조이다.

돌더미, 작장더미, 쓰레기 더미...처럼 위로 갈수록 노드의 수가 줄어드는 모습을 하고 있다.

 

 

1-2. 힙의 종류

• 최대 힙(Max Heap): (완전 이진 트리) + (부모 노드 > 자식 노드)
• 최소 힙(Min Heap): (완전 이진 트리) + (부모 노드 < 자식 노드)

 

힙은 위처럼 두 종류로 나뉜다.

다시 풀어서 설명하자면

최대 힙은 완전 이진 트리이면서 부모 노드가 자식 노드보다 큰 트리

최소 힙은 완전 이진 트리이면서 부모 노드가 자식 노드보다 작은 트리이다.

 

보통 힙이라고 하면 일반적으로 최대 힙을 의미한다.

 

 

1-3. 힙의 활용

힙은 최댓값 혹은 최솟값을 빠르게 찾아내기에 유리한 자료구조이다.

그래서 우선순위 큐를 구현할 때 쓰이기도 하고

허프만 코드를 구현할 때도 쓰이고

힙 정렬을 구현할 때도 쓰인다.

 

 

1-4. 예시(힙 삽입)

이번 목차에서는 위 7개의 숫자를 가지고 힙을 만드는 과정을 보일 것이다.

힙을 만들기 위해서는 값 삽입 -> 힙 구조로 변경 -> 값 삽입 -> 힙 구조로 변경 ->... 을 계속 반복해주면 된다.

값을 넣을 때 힙 구조가 붕괴되는 경우가 있어 이 과정을 반복하는 것이다.

예시를 통해 알아보자.

 

 

• 첫 번째 값(5) 삽입

 

우선 첫 번째 값부터 차례대로 트리에 넣어준다.

'5'를 트리에 넣었다.

 

 

• 두 번째 값(2) 삽입

 

이번에는 '2'를 넣었다.

부모 노드(5)가 자식 노드(2) 보다 크기 때문에 swap을 하지 않고 넘어간다.

 

 

• 세 번째 값(6) 삽입

 

 

이번에는 '6'을 넣었다.

부모 노드(5)가 자식 노드(6) 보다 작기 때문에 힙 구조가 붕괴되었다.

따라서 두 값을 swap 해주어야 한다.

 

 

swap을 하고 나면 위와 같은 트리 모양으로 바뀐다.

힙은 이렇게 항상 부모 노드가 자식 노드보다 커야 한다는 조건이 있다.

그래서 매번 값이 들어올 때마다 값을 비교하고 swap을 해줘야 한다.

자식 노드들 끼리는 값을 비교하지 않는다. 즉, 위 예시에서 2와 5는 비교하지 않는다는 것이다.

 

 

• 네 번째 값(1) 삽입

 

이번에는 '1'을 넣었다.

부모 노드(2)가 자식 노드(1)보다 크기 때문에 swap을 하지 않는다.

 

 

• 다섯 번째 값(3) 삽입

'3'을 넣었다.

부모 노드(2)가 자식 노드(3) 보다 작기 때문에 swap을 해줘야 한다.

 

 

swap을 하여 힙 구조로 변경하였다.

 

 

• 여섯 번째 값(4) 삽입

 

부모 노드(5)가 자식 노드(4) 보다 크기 때문에 swap을 하지 않는다.

 

 

• 일곱 번째 값(7) 삽입

 

부모 노드(5)가 자식 노드(7) 보다 작기 때문에 swap을 해준다.

 

 

이번엔 부모 노드(6)가 자식 노드(7) 보다 작기 때문에 또다시 swap을 해준다.

 

 

• 완성된 최대 힙 구조

 

이렇게 해서 힙 구조가 완성되었다.

완전 이진 트리이면서 부모 노드가 자식 노드보다 큰 트리 구조이다.

이러한 과정을 통해 '7'이라는 최댓값을 빠르게 찾을 수 있는 구조가 바로 힙 인 것이다.

 

 

완성된 힙 구조를 일렬로 나열해보자.

트리 모양으로 봤을 땐 뭔가 숫자들이 정렬되어 보였는데 막상 이렇게 보니 뒤죽박죽인 느낌이다.

힙 구조는 최댓값(혹은 최솟값)을 빨리 찾기 위한 구조이지 이걸 사용했다고 정렬이 되지는 않기 때문이다.

 

힙 구조를 만들기 위해서 힙 삽입 -> 힙 구조로 변경 -> 힙 삽입 -> 힙 구조로 변경을 반복했다면

정렬을 하기 위해서는 힙 삭제 -> 힙 구조로 변경 -> 힙 삭제 -> 힙 구조로 변경을 반복해야 한다.

이 과정을 통틀어 힙 정렬이라고 하며 이에 대해서는 다음 포스팅에서 이어진다.

 

 

---

💡 느낀 점

• 우선순위 큐에 값을 넣으면 그때마다 알아서 정렬을 해주는 줄 알았다. 힙 구조를 사용하는 거니까 최대 힙 구조로 유지하다가 값을 빼면 다시 힙 구조로 변경하는 거였군...
• 힙을 배웠는데 이게 대체 힙 영역이랑 무슨 관계가 있는 건지 궁금했다. 이에 대해 찾아본 자료를 밑에 링크에 달아두었다.

📘 참고한 자료

• Heap Sort 정렬 알고리즘 - ZeddiOS님 블로그
• 힙 트리 - 나무위키
• 힙 영역과 힙 알고리즘의 관계 - OKKY

 

---