힙(Heap) vs 이진 탐색 트리(Binary Search Tree)

힙(Heap)이란?

힙(Heap)은 완전 이진 트리(Complete Binary Tree)를 기반으로 하는 자료구조로서, 힙에 데이터를 저장해 놓으면 O(1), 즉 상수 시간에 최솟값이나 최댓값에 접근할 수 있다. 이것이 가능한 이유는 힙이 최솟값 또는 최댓값을 트리의 루트(root)에 저장해 놓기 때문이다.

 

보통, 최솟값을 트리의 루트에 위치시키는 힙을 최소 힙(Min Heap)이라고 하고, 최댓값을 트리의 루트에 위치시키는 힙을 최대 힙(Max Heap)이라고 한다.

 

최대 힙과 최소 힙

 

힙에서 값을 연속해서 꺼내면 자동으로 정렬되는 효과가 나기 때문에 기본적으로 정렬에 활용할 수 있다. 몇 번째로 가장 작은 값 또는 가장 큰 값을 구해야 하는 상황에서도 유용하게 사용할 수 있다. 예를 들어, 3번째로 작은 값이 필요하다면 최소 힙에서 3번 값을 꺼내면 된다.

 

• 완전 이진 트리(Complete Binary Tree)의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다
• 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리는 중복된 값을 허용하지 않는다.)

 

이진 트리(Binary Tree)란?

노드의 최대 자식 노드가 2인 트리를 말한다.

최대 2개이기 때문에 자식 노드가 없을 수도 아니면 1개만 있을 수도 있다.

 

이진 탐색 트리(Binary Search Tree)란?

노드의 최대 자식 노드가 2인 이진 트리 구조에 다음의 특성을 가진 트리이다.

 

• 각 노드에 중복되지 않는 키를 가진다.
• 왼쪽 자식 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가진다.

 

완전 이진 트리(Complete Binary Tree)란?

왼쪽에서 오른쪽으로 노드가 순서대로 꽉 채워진 이진트리를 말한다.

 

• 마지막 노드를 제외하고는 모든 노드가 채워져있어야 한다.
• 위에서 아래로, 왼쪽에서 오른쪽 방향으로 채워져야 한다. 중간에 빈 노드가 있어서는 안 된다.

완전 이진 트리의 형태

 

힙(Heap)과 이진 탐색 트리(Binary Search Tree)

둘 다 이진 트리(Binary Tree)라는 공통점이 있다.

• 이진 탐색 트리의 노드 값의 크기는 부모 노드 < 왼쪽 노드 < 오른쪽 노드 순이다.
• 힙은 각 노드의 값이 자식 노드보다 크거나 같다 또는 작거나 같다.
• 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건이 없음
• 힙은 완전 이진 트리이므로, 무조건 왼쪽 자식 노드부터 데이터를 삽입한다.
• 힙은 데이터의 중복을 허용한다.

이진 탐색 트리는 정말 탐색을 위한 트리구조

힙은 최대/최소값을 구하기 위한 자료구조

 

힙(Heap)의 맹점

힙은 내부 구조를 항상 최솟값 또는 최댓값을 제공하기 위한 최적의 상태로 유지해야 한다.

즉, 최솟값이나 최댓값을 항상 트리의 루트(root)에 위치시켜야 한다. 이 말은 힙에 값을 추가할 때마다 내부적으로 트리 상에서 값들이 재배치되어야 한다는 것이다.

 

힙을 구현할 때 완전 이진트리를 사용하는 이유는 값을 추가할 때 들어가는 시간적인 비용을 'O(log n)'으로 제한할 수 있기 때문이다. 이것은 완전 이진트리의 높이가 'log₂(n)'이기 때문이다.

 

예를 들어, 최소 힙을 기준으로 생각해 보면, 최악의 경우 현재 힙에 저장되어 있는 모든 값보다 더 작은 값이 추가될 수 있을 텐데 그러면 그 값은 트리의 말단(leaf)부터 시작해서 최상단의 루트까지 자기보다 작은 값들과 자리를 계속 바꾸면서 올라가야 한다. 그래서 비어있는 힙에 데이터를 저장해야 하는 상황이라면 완전히 이야기가 달라질 수 있는데, 저장해야 하는 값의 개수를 n이라고 하면, 모든 값을 저장하는 'O(n * log n)'의 시간이 소요된다.

 

따라서 힙에 데이터를 저장하는데 소요되는 시간을 고려하지 않으면 오히려 안 쓰니만 못한 자료구조가 될 수도 있다. 예를 들어 배열에서 최솟값을 구하기 위해서 힙을 사용하는 것은 배보다 배꼽이 더 큰 상황이 된다. 그냥 간단하게 선형 탐색을 하면 'O(n)' 시간에 해결될 일이, 괜히 힙을 사용해서 'O(n*log(n))'의 시간으로 처리하는 꼴이 되기 때문이다.

 

코딩 테스트에서 활용

위에서 설명드린 맹점 때문에 힙은 전체 데이터를 저장해야 하는 문제에서는 득보다는 해가 되는 경우가 많다.

하지만 일부 데이터만을 저장할 수 있는 상황에서는 힙이 큰 힘을 발휘한다.

 

대표적인 예로 'k'번째로 작은 값이나 큰 값을 구하는 유형의 문제를 들 수 있다. 크기가 'k'인 힙 하나만 있으면 이러한 문제는 아주 수월하게 해결이 가능하다.

 

예를 들어서, 'k'번째로 작은 값이 필요하다면 최대 힙을 사용하면 된다. 그리고 'k'번째로 큰 값이 필요하다면 최소 힙을 사용하면 된다.

 

기본 아이디어는 다음과 같다. 만약에 'k'번째로 큰 값을 구하려고 한다면,

 

• 주어진 데이터 세트(배열, 집합, 링크드 리스트, 등등)를 처음부터 끝까지 차례로 스캔해 나간다.
• 처음 'k'개의 값은 무조건 최소 힙에 넣어서 최소 힙을 우선 꽉 채운다.
• 그다음부터는 최소 힙에 저장되어 있는 가장 작은 값과 새로운 값을 비교한다.
  • 기존에 최소 힙에 저장되어 있던 값이 더 작다면 그 값을 최소 힙에서 제거하고 새로운 값을 최소 힙에 추가한다.
  • 새로운 값이 더 작다면 다음 값으로 넘어간다.
• 이 과정을 마지막 값까지 반복해 주면 최종적으로 최소 힙에는 여태까지 나온 가장 큰 'k'개의 값만이 남는다.

'k'번째로 큰 값을 찾는데 최소 힙을 사용한다는 점이 처음에는 반대인 것같이 느껴져서 바로 이해가 어려울 수도 있다. 하지만 천천히 위 과정을 종이에 그리면서 따라가다 보면 이해가 될 것이다.

 

함께 읽으면 좋은 글

<히프> 기본 개념과 삽입 삭제 알고리즘 정리

 

[자료구조] 트리, 힙, 시간복잡도

출처

알고달레