[CS] 힙(Heap)을 알아보자

힙 (Heap)

가장 일반적인 우선 순위 큐의 구현 방법으로 완전 이진 트리를 기본으로 한다.

힙을 사용해 우선 순위 큐를 구현하면 요소의 삽입, 삭제를 O(log n) 시간 복잡도로 수행한다.

 

우선 순위 큐(Priority Queue)란?

여러 항목들 중 가장 중요한 항목을 먼저 꺼낼 수 있는 자료구조다.

각 요소에 우선 순위를 할당해 저장하고, 우선 순위가 가장 높은 요소에 대해 빠르게 접근 및 삭제할 수 있다.

힙은 바로 이런 우선 순위 큐의 구현 방법 중 하나인 것이다.

 

완전 이진 트리(full binary tree)

먼저 이진 트리(binary tree)란 모든 노드들이 둘 이하의 자식을 가진 트리를 말한다.

 

이진 트리

 

완전 이진 트리는 마지막 레벨(제일 아래쪽)을 제외하고 모든 레벨이 완전히 채워져 있는 트리다.

마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽 -> 오른쪽으로 채워져야 한다.

 

완전 이진 트리

 

예시로 나온 노드 20이 삽입되어야 할 때, 12의 오른쪽에 둘 것인지 8의 왼쪽에 둘 것인지 헷갈렸다.

만약 8의 왼쪽에 둔다면 12와 8이 있는 2번째 레벨이 완전히 채워지지 않는 상태가 된다.

완전 이진 트리는 최하단을 제외하고 모든 레벨이 완전히 채워져야 하기 때문에 왼쪽 노드인 12를 먼저 완전하게 만들어줘야 한다.

따라서 위와 같은 그림으로 데이터가 형성되며 이러한 형태를 완전 이진 트리라고 할 수 있다.

---

최소 힙과 최대 힙

힙을 통해 최댓값이나 최솟값을 찾아내기 쉬운데, 이는 힙에 최소 힙과 최대 힙이 있기 때문이다.

 

최소 힙이란 작은 값이 항상 트리의 위에 있게 해, 트리의 루트(꼭대기)에는 가장 작은 값이 와야 한다.

반대로 최대 힙이란 가장 큰 값이 맨 위에 오며, 모든 노드들은 자기 부모 노드보다 큰 값을 가지고 있다.

 

최소 힙을 예시로, 만약 최솟값이 꺼내지면 어떻게 될까?

위 그림에서 최솟값은 1이다. 1이 사라지고 나면 루트는 비어 있는 상태가 된다.

 

이 빈 자리를 채우기 위해 완전 이진 트리의 맨 마지막 노드(가장 마지막에 추가된 노드)를 가져오게 된다.

위 그림으로 보면 가장 마지막에 추가된 노드는 5가 될 것이다.

 

         5

        / \

      2  3

    / 

  4 

 

이 때 5는 자기 자식 노드와 비교해서 자기보다 작은 노드와 자리를 바꾼다.

 

         2

        / \

      5  3

    / 

  4 

 

내려 와서 또 자식 노드와 비교해서 자기보다 작을 경우 자리를 바꾼다.

 

         2

        / \

      4  3

    / 

  5 

 

이렇게 최소 힙이 유지되었다. 최대 힙은 여기서 최댓값으로 바꿔 진행하면 된다.

이러한 교환을 버블이라고 한다.

---

힙의 시간복잡도

처음에 힙의 시간 복잡도는 O(log n)이라고 했다.

 

배열에서 특정 값을 찾을 때 최악의 경우 모든 배열을 다 뒤져야 하기 때문에 O(n)이 나오게 된다.

 

위 그림에서 힙은 최대 힙을 유지하고 있다. 

 

높이가 1일 때 노드는 20, 1개밖에 없다.

하지만 높이가 2일 때는 노드 20, 17, 8로 노드의 개수는 총 3개가 된다.

높이가 3일 때는 노드 20, 17, 8, 5, 12로 노드의 개수는 5개가 되는데 이를 2**h -1 로 정리할 수 있다.

 

따라서 모든 경우를 다 돈다고 최악의 경우를 가정하면 O(log n) 시간 복잡도가 소요될 수 있다.

---

**참고

 

- 구름톤 13조 홍삼보다13의 윤수님 발표자료

- 자바스크립트 힙 구현

[자료구조] JavaScript로 힙(Heap) 구현하기

- 유튜버 엔지니어 대한민국님 바이너리 힙