최소값이나 최대값에 접근하는데 최적화된 자료구조 힙(heap)에 대해서 알아보겠습니다.
힙이란?
힙은 완전 이진 트리(Complete Binary Tree)를 기반으로 하는 자료구조로서, 힙에 데이터를 저장해놓으면 O(1), 즉 상수 시간에 최소값이나 최대값에 접근할 수 있습니다. 이 것이 가능한 이유는 힙이 최소값 또는 최대값을 트리의 루트(root)에 저장해놓기 때문인데요. 보통, 최소값을 트리의 루트에 위치시키는 힙을 최소힙(Min Heap)이라고 하고, 최대값을 트리의 루트에 위치시키는 힙을 최대힙(Max Heap)이라고 하죠.
따라서 최소힙은 아래와 같은 형태로 값을 저장하고,
1
/ \
3 2
/ \ /
4 6 5반면에 최대힙은 아래와 같은 형태로 값을 저장합니다.
6
/ \
5 3
/ \ /
4 2 1힙에서 값을 연속해서 꺼내면 자동으로 정렬되는 효과가 나기 때문에 기본적으로 정렬에 활용할 수 있고요. 몇 번째로 가장 작은 값 또는 가장 큰 값을 구해야하는 상황에서도 유용하게 사용할 수 있습니다. 예를 들어, 3번째로 작은 값이 필요하다면 최소힙에서 3번 값을 꺼내면 됩니다.
힙의 맹점
힙은 내부 구조를 항상 최소값 또는 최대값을 제공하기 위한 최적의 상태로 유지해야하는데요. 즉, 최소값이나 최대값을 항상 트리의 루트에 위치시키야 합니다. 이 말은 힙에 값을 추가할 때 마다 내부적으로 트리 상에서 값들이 재배치가 필요하다는 뜻이죠.
힙을 구현할 때 완전 이진 트리를 사용하는 이유는 값을 추가할 때 들어가는 시간적인 비용을 O(log n)으로 제한할 수 있기 때문입니다.
이 것은 완전 이진 트리의 높이가 log₂(n)이기 때문이죠.
예를 들어, 최소힙을 기준으로 생각해보면, 최악의 경우 현재 힙에 저장되어 있는 모든 값보다 더 작은 값이 추가될 수 있을텐데요. 그러면 그 값은 트리의 말단(leaf)부터 시작해서 토리의 최상단(root)까지 자기보다 작은 값들과 자리를 계속해서 바꾸면서 올라가야합니다.
그래서 비어있는 힙에 데이터를 저장해야하는 상황이라면 완전히 얘기가 달라질 수 있는데요.
저장해야하는 값의 개수라고 n이라고 하면, 모든 값을 저장하는데 O(n * log n)의 시간이 소요됩니다.
따라서 힙에 데이터를 저장하는 데 소요되는 시간을 고려하지 않으면 오히려 안 쓰니만 못한 자료구조가 될 수도 있습니다.
예를 들어, 배열에서 최소값을 구하기 위해서 힙을 사용하는 것은 배보다 배꼽이 더 큰 상황이 됩니다.
그냥 간단하게 선형 탐색을 하면 O(n) 시간에 해결될 될 일을, 괜히 힙을 써서 O(n * log n)의 시간이 처리하는 꼴이기 때문이죠.
코딩 테스트에서 활용
위에서 설명드린 맹점 때문은 힘은 전체 데이터를 저장해야하는 문제에서는 득보다 해가 되는 경우가 많습니다. 하지만 일부 데이터만을 저장할 수 있는 상황에서는 힙이 큰 빛을 발휘할 수 있습니다.
대표적인 예로, k 번째로 작은 값이나 큰 값을 구하는 유형의 문제를 들 수 있는데요.
크기가 k인 힙 하나면 있으면 이러한 문제는 아주 수월하게 해결할 수 있습니다.
예를 들어서, k 번째로 작은 값이 필요하다면 최대힙을 사용하면 됩니다.
(네, “최소힙” 아니고 “최대힙” 입니다. 오타 아닙니다.)
그리고 k 번째로 큰 값이 필요하다면 최소힙을 사용하면 됩니다.
햇갈리실 것 같아서 부연 설명을 드리면 기본 아이디어는 다음과 같습니다.
만약에 k 번째로 큰 값을 구하려고 한다면,
- 주어진 데이터 세트(배열, 집합, 링크드 리스트, 등등)를 처음부터 끝까지 차례로 스캔해나갑니다.
- 처음
k개의 값은 무조건 최소힙에 넣어서 우선 꽉 채웁니다. - 그 다음부터는 최소힙에 저장되어 있는 가장 작은 값과 새로운 값을 비교하는데요.
- 기존에 최소힙에 저장되어 있던 값이 더 작다면 그 값을 최소힙에서 제거하고 새로운 값을 최소힙에 추가힙니다.
- 새로운 값이 더 작다면 다음 값으로 넘어갑니다.
- 이 작업을 마지막 값까지 반복해주면 최종적으로 최소힙에는 여태까지 나온 가장 큰
k개의 값만 남을 것입니다.
k 번째 큰 값을 찾는데 최소힙을 사용한다는 점이 처음에는 반대인 것 같이 느껴져서 바로 이해가 어려우실 수도 있습니다.
하지만 천천히 위 과정을 종이에 그리면서 따라가시다보면 왜 그런지 이해가 되실 거에요.
추천 문제
실전 테스트에서 힙 자료구조를 어떻게 활용하실 수 있는지 감을 잡으시는데 아래 문제를 추천드리겠습니다.