자료구조 - 힙

힙(Heap)

---

힙은 완전 이진트리의 일종으로 부모 노드와 자식 노드 간에 특정한 조건을 만족하는 자료구조이다.

이진 트리에 대해서 잘 모른다면 밑의 글을 읽고 나서 힙을 공부해 보자.

자료구조 - 이진 트리(Binary Tree)

 

힙의 특징

---

힙 자료구조에는 여러 가지 특징이 있는데 하나씩 살펴보자.

1. 힙은 완전 이진트리다. 즉, 왼쪽에서 오른쪽으로 채워지는 마지막 수준을 제외하고 트리의 모든 수준이 완전히 채워진다. 이 속성은 트리가 배열을 사용하여 효율적으로 표현되도록 보장한다.

2. 힙 유형에 따라 데이터가 항상 트리의 루트 노드에 있도록 보장한다. 추후에 알아볼 최대 힙, 최소 힙 구성에 따라서 트리의 루트 노드에는 항상 최댓값이나 최솟값이 있도록 보장할 수 있다.

3. 부모 노드와 그 자식 사이의 관계는 공식에 의해 제공된다. 힙의 유형에 대해서 알아보면서 어떤 공식이 있는지 확인해 보자.

4. 새로운 데이터는 가장 오른쪽 아래 수준에서 사용 가능한 다음 위치에 삽입되고 요소를 상위 요소와 비교하고 필요한 경우 교체하여 힙 속성이 복원된다. 루트 요소를 제거하려면 마지막 요소로 교체하고 아래로 쌓이는 작업이 포함된다.

5. 최소 또는 최대 값은 항상 힙의 루트에 있으므로 지속적인 액세스가 가능하다.

 

힙의 유형

---

힙은 일반적으로 최대 힙, 최소 힙 총 두 가지 유형이 있다.

최대 힙은 자식 노드보다 부모 노드의 값이 큰 힙 자료구조를 의미하고, 최소 힙은 자식 노드보다 부모 노드의 값이 작은 것을 의미한다.

각 유형을 차례대로 살펴보자.

 

최대 힙(Max-Heap)

최대 힙은 힙에서 루트 노드의 값은 모든 하위 노드 중에서 가장 커야 하며 왼쪽 및 오른쪽 하위 트리에도 동일한 작업이 수행되어야 한다.

힙은 보통 배열을 이용해서 구현하게 되는데 상위 노드와 왼쪽, 오른쪽 자식 노드를 구하는 3가지 공식을 사용하여 트리를 구성할 수 있다.

1. 상위 노드: Arr[(n-1)/2]
2. 왼쪽 자식 노드: Arr[(2 * n) + 1]
3. 오른쪽 자식 노드: Arr[(2 * n) + 2]

참고로 해당 공식들은 최소 힙에서도 똑같이 적용된다.

그림을 통해서 위의 3가지 공식을 직접 사용해 보며 상위 노드와 왼쪽, 오른쪽 노드를 구해보자.

먼저 9번 노드를 기준으로 잡고 상위 노드를 구해보면 n = 1 이기 때문에 Arr[(1 - 1) / 2]가 되고 Arr[0] 값이 나오게 된다.

하지만 그림에서 살펴봤듯이 Arr[0]은 존재하지 않는 값이기 때문에 해당 노드는 상위 노드가 없다는 것을 알 수 있고 즉, 루트 노드임을 확인할 수 있다.

그다음으로 왼쪽 자식 노드를 구해보면 Arr[(2 * 1) + 1]로 대입할 수 있고 Arr[2] 값이 나오게 된다. 이를 통해서 9번 노드의 왼쪽 자식 노드는 현재 배열에서 2번째 값임을 알 수 있고 배열의 2번 인덱스에 접근해 7번 노드인 것을 알 수 있다.

마지막으로 오른쪽 자식 노드를 구해보면 Arr[(2 * 1) + 2] 이므로 Arr[3] 값이 나오게 된다. 이를 통해서 9번 노드의 오른쪽 자식 노드는 배열에서 3번째 값으로 5번 노드인 것을 알 수 있다.

 

최소 힙(Min-Heap)

최소 힙은 힙에서 루트 노드의 값은 모든 하위 노드 중에서 가장 작아야 하며 왼쪽 및 오른쪽 하위 트리에도 동일한 작업이 수행되어야 한다.

이전에 살펴본 최대 힙에서 반대 개념으로 생각하면 이해하기 쉬울 것 같다.

상위 노드와 왼쪽, 오른쪽 노드를 구하는 공식은 최대 힙에서 사용했던 것과 동일하다. 따라서 상위 노드부터 구해보면 Arr[(1 -1) / 2] 를 구하면 Arr[0]이기 때문에 1번 노드는 상위 노드를 가지고 있지 않으면서 루트 노드인 것을 알 수 있다.

다음으로 왼쪽 노드를 구해보면 Arr[(2 - 1) + 1] 이므로 Arr[2]가 된다. 해당 인덱스에 있는 값을 확인하면 5번 노드가 1번 노드의 왼쪽 자식 노드인 것을 알 수 있다.

마지막으로 오른쪽 노드를 구해보면 Arr[(2 - 1) + 2] 이므로 Arr[3]이 되고 해당 인덱스에 있는 값을 확인해 보면 3번 노드가 1번 노드의 오른쪽 자식 노드인 것을 알 수 있다.

 

힙의 동작 과정

---

최대 힙을 예시로 삽입과 삭제가 어떻게 동작하는지 알아보자.

처음에 9번 노드가 삽입되었다고 가정하고 진행을 해봤다.

 

데이터 삽입

새로운 데이터로 7번 노드가 삽입되면 먼저 부모 노드를 기준으로 왼쪽 최하단에 위치시킨다.

그런 다음 해당 노드와 부모 노드를 비교하여 부모 노드보다 작을 시 그 자리에 위치시키고, 값이 부모 노드보다 크다면 부모 노드와 위치를 바꿔가며 해당 과정을 반복한다.

만약 새로운 데이터로 10번 노드가 삽입된다고 가정했을 때 부모 노드인 9번과 비교하여 10이 더 크기 때문에 10번 노드의 위치와 9번 노드의 위치를 변경해 준다.

이러한 과정을 계속 반복해 주면 최대 힙 자료구조를 구성할 수 있다.

 

데이터 삭제

힙은 최대 힙이나 최소 힙으로 구성되는데 따라서 데이터 삭제가 이뤄지면 가장 큰 값이거나 가장 작은 값인 부모 노드부터 삭제된다.

데이터 삭제도 최대 힙을 기준으로 어떻게 동작하는지 알아보자.

최대 힙 자료구조가 위의 그림과 같이 구성되어 있다고 가정해 보자.

데이터를 삭제하면 먼저 최상단 노드 즉, 현재 자료구조 상에서 가장 큰 값인 9번 노드가 삭제된다.

부모 노드를 삭제한 뒤 가장 최하단에 위치한 자식 노드인 6번 노드를 전에 삭제했던 부모 노드의 위치로 옮긴다.

최대 힙 구성을 유지하기 위해 새로 위치한 부모 노드의 값 보다 큰 자식 노드가 있는지 비교하고 큰 값이 있다면 새로 위치한 부모 노드와 위치를 변경한다.

 

여기서 주의할 점이 하나 있는데 왼쪽 자식 노드와 오른쪽 자식 노드가 새로 위치한 부모 노드보다 값이 클 경우이다.

예를 들어 부모 노드가 6인데 자식 노드가 7, 8인 경우를 생각해 보자.

두 자식 노드 모두 부모 노드보다 값이 클 경우 자식 간의 비교가 필요하게 된다.

 

새로 위치한 부모 노드인 6번 노드를 기준으로 왼쪽 자식 노드인 7번 노드와 오른쪽 자식 노드인 8번 노드 둘 다 부모 노드보다 값이 크기 때문에 자식 노드끼리 비교하게 된다.

7번 노드보다 8번 노드가 더 커서 부모 노드인 6번 노드와 위치를 변경해 주므로 최대 힙 구성을 유지할 수 있게 된다.

 

힙의 장단점

---

힙의 장점

힙은 최대 힙이나 최소 힙으로 구성하면 항상 루트 노드에 최솟값과 최댓값이 위치하기 때문에 최대 및 최소 요소에 대한 빠른 액세스 O(1)를 제공한다.

힙은 특정한 순서에 따라 정렬된 상태를 유지하므로 효율적인 삽입 및 삭제 작업 O(log n)을 제공하여 요소들의 우선순위에 따라 빠르게 작업을 처리할 수 있다.

 

힙의 단점

힙은 정렬된 상태를 유지하려고 하지만 완벽히 정렬되지 않을 수 있다.

앞서 살펴본 장점과는 다르게 루트 노드에 위치한 최댓값과 최솟값 이외의 최대 및 최소 요소는 보장하지 않기 때문에 루트 노드를 제외하고 요소를 탐색하는 데 적합하지 않다.

힙은 정렬된 상태를 유지하기 위해 삽입과 삭제 작업을 진행할 시 정렬을 재조정해야 된다. 따라서 일정한 메모리 오버헤드를 발생시킬 수 있다.

 

힙 사용 사례

데이터를 큐나 배열에 넣고 최댓값이나 최솟값을 찾으려면 최악의 경우에는 하나씩 값을 다 비교하여 O(N)의 시간복잡도를 가질 수 있다. 반면에 힙을 사용하게 되면 시간 복잡도 측면에서 상당히 줄일 수 있다.

앞서 설명했던 것과 같이 데이터를 큐에 넣고 최대 및 최소 요소를 찾으려면 성능적인 부분에서 떨어질 수 있다. 이때 사용되는 자료구조가 우선순위 큐인데 일반적으로 힙을 이용하여 구현하게 된다.

우선순위가 중요한 운영체제 작업 스케줄링 등에서 사용된다.