1. 힙 (Heap) 이란?
힙(Heap)이란 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)이다. 완전 이진 트리란 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리이다.
힙을 사용하는 이유는 다음과 같다.
- 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸리는 반면, 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(log n)이 걸린다.
- 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다.
즉, 최대값과 최소값을 찾는 기능이 필요할 때, 힙(Heap) 자료구조를 사용하면 매우 효율성을 높일 수 있는 것이다. 힙이란 자료구조는 트리를 기반으로 하는 변형된 형태의 정책을 쓰고 있다.
2. 힙 (Heap) 구조
힙은 최대값을 구하기 위한 구조인 '최대 힙(Max Heap)'과 최소값을 구하기 위한 구조인 '최소 힙(Min Heap)'으로 분류할 수 있다.
힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조이다.
- 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
- 완전 이진 트리 형태를 가짐
(최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음)
위 그림을 보면, 위 붉은 사각형 안에 있는 노드 중 가장 큰 노드는 15이다. 10, 3, 4의 값을 가지는 노드 중 가장 큰 노드는 10이다. 최대 힙의 경우 각 노드의 값은 자식 노드의 값보다 크거나 같은 것이다.
최대 힙(Max Heap)에는 맨 위에 가장 큰 값이 있고, 최소 힙(Min Heap)에는 맨 위에 가장 작은 값이 있다고 이해하면 된다. 힙의 구조를 구성하면 맨 위에 있는 Root Node만 가져오는 것이고, 이것은 최대값이나 최소값을 찾는 상황에서 효율성이 매우 높다.
힙과 이진 탐색 트리의 공통점과 차이점
| 공통점 | 힙과 이진 탐색 트리는 모두 이진 트리이다. |
| 차이점 | - 힙은 각 노드의 값이 자식 노드보다 크거나 같다(Max Heap의 경우) - 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 크다. - 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건이 없다. (힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있다.) |
결국, 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 된다.
3. 힙 (Heap) 동작
데이터를 힙 구조에 삽입, 삭제하는 과정을 그림을 통해서 선명하게 이해해 보겠다.
힙에 데이터 삽입하기 - 기본 동작
힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입된다.
위 그림을 보면, 먼저 데이터 15가 있고, 그 다음에 10은 무조건 Root Node의 왼쪽 자식부터 채운다. 그 다음 들어온 8은 Root Node의 오른쪽 자식으로 넣는다. 완전 이진 트리기 때문에 자식은 두 개밖에 가질 수 없다. 또 5가 들어오면 이번에는 Root Node의 왼쪽 자식인 10의 왼쪽 자식으로 넣는다. 즉, 왼쪽부터 채워지고 나서 자식 노드들이 쭉 채워지는 것이다.
힙에 데이터 삽입하기 - 삽입할 데이터가 힙의 데이터보다 클 경우 (Max Heap의 예)
위의 기본 동작 그림 상황에서, 20의 값을 가지는 노드를 추가하는 경우를 그림으로 보면 다음과 같다.
이런 경우, 먼저 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워진다. 그리고 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복한다. (swap)
위 그림에서 우선 20을 최하단부 왼쪽부터 넣을 순서에 넣었다. 처음에는 크기를 따지지 않고 바로 최하단부 왼쪽에 삽입하는 것이다. 그리고 20을 부모 노드인 8과 비교해 더 크니 두 노드의 위치를 바꿨다(swap). 해당 작업을 반복해 Root Node인 15와 20을 swap 하여 20이 Root Node가 되었다. 만약 20이 아니라 13의 값을 가지는 노드가 추가되었다면, Root Node가 바뀌지는 않았을 것이다.
힙의 데이터 삭제하기 (Max Heap의 예)
보통 삭제는 최상단 노드(root node)를 삭제하는 것이 일반적이다. 왜냐하면 힙의 용도는 최대값 또는 최소값을 root node에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것이기 때문이다.
상단의 데이터를 삭제하면 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지막에 추가한 노드)를 root 노드로 이동시킨다. 그런 다음, root node의 값이 child node보다 작을 경우, root node의 child node 중 가장 큰 값을 가진 노드와 root node 위치를 바꿔주는 작업을 반복한다. (swap)
위 그림과 같이 힙이 구현이 되어 있을 때, 최대값(root node)인 20을 삭제하면 일단 가장 마지막에 들어갔던 8을 root node로 올린다. 그 다음에, 이 루트 노드를 기준으로 자식 노드 둘과 비교해서 자식 노드 중에 더 큰 값을 찾아서 그 큰 값과 root node를 비교한다. 그렇게 해서 root node의 값이 더 작으면 swap을 한다. 또 자식 노드들과 비교해서 swap 하는 과정을 반복해서 힙을 완성시킨다.
[참고자료]
패스트캠퍼스 개발자 취업 합격 패스 With 코딩테스트, 기술면접 초격차 패키지 Online 강의자료
'Data Structure & Algorithm' 카테고리의 다른 글
| 힙 (Heap) (3) (0) | 2023.01.10 |
|---|---|
| 힙 (Heap) (2) (1) | 2023.01.06 |
| 트리 (Tree) (3) (0) | 2023.01.04 |
| 트리 (Tree) (2) (0) | 2023.01.03 |
| 트리 (Tree) (0) | 2023.01.02 |
