힙(Heap)이란?

힙(Heap)이란?

힙(Heap)이란 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리의 한 종류이다. 힙은 일종의 반정렬 상태(느슨한 정렬 상태)를 유지하는데 최대 힙(max heap)의 경우 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크고, 최소 힙(min heap)의 경우 부모 노드의 키 값보다 항상 작다. 이진 탐색 트리에서는 중복된 값을 허용하지 않는 반면, 힙 트리에서는 중복된 값을 허용한다.

출처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

힙의 인덱스 값

heap의 index 순서 출처 : https://velog.io/@gnwjd309/data-structure-heap

힙의 인덱스를 잠시 보고 넘어가자면 최상위 부모 노드의 인덱스는 1, 그 다음 왼쪽 아래 자식 노드부터 2, 3 순서이다.

- 부모 노드의 인덱스 = 자식 노드 인덱스 // 2

- 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2

- 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1

위와 같은 규칙을 가지는데 최상위 부모 노드의 인덱스를 1로 보기때문에 배열로 구현할 시 인덱스를 0은 제외하고 1부터 시작하는 것이 편하다.

 

힙(Heap)의 삽입

힙은 새로운 요소가 들어오면 우선 가장 마지막 노드에 요소를 삽입한다. 그 다음 새로운 노드를 부모 노드와 비교해서 힙의 성질을 만족하도록 교환하는 과정을 거치게 된다. 아래 그림을 보면 조금 더 이해가 쉽다.

 

최대 힙(max heap)을 기준으로 [15, 10, 8, 3, 4]라는 배열을 힙으로 만든다고 생각해보자.

위와 같이 순서대로 내려가면서 왼쪽에서 오른쪽 부터 한칸 씩 채우게 된다.

만약 이러한 상황에서 기존의 힙의 요소들 보다 큰 수가 삽입된다면 어떻게 될까? 아래는 20을 추가로 삽입했을 때를 보도록 하겠다.

1. 우선 20을 가장 하단에 삽입한다. 그 후 부모 노드인 8과 비교한다. 최대 힙이기 때문에 자식노드 20이 부모노드 8보다 크기 때문에 자리를 바꿔준다.

2. 다음 다시 부모노드인 15와 비교한다. 최대 힙이기 때문에 20과 15의 자리를 바꿔주면 된다. 이러한 과정을 통해 힙의 삽입을 완료할 수 있다.

 

힙(Heap)의 삭제

힙에서 삭제를 한다는 것은 힙의 가장 최상단 노드의 요소를 제거한다는 의미이다. 고로 최대힙의 경우 가장 큰 수, 최소힙의 경우 가장 작은 수가 제거된다고 생각하면 된다. 아래 이미지를 통해 한번 보자

1. 위와 같은 힙이 있을 때 가장 최상단 노드는 20이기 때문에 여기서 삭제를 한다는 것은 20을 제거한다는 것이다.

2. 최상단 요소를 제거한 후 중요한 점은 무조건 가장 마지막 노드(최하단 최우측 노드)를 최상단 노드로 옮겨준다는 것이다. 그렇게 때문에 8을 최상단으로 올린 후 아래 자식노드들과 비교를 한다. 8보다 15가 더 크고 현재 최대힙이기 때문에 15와 8의 자리를 바꿔준다. 이러한 과정을 통해 힙의 삭제를 완료할 수 있다.

 

힙의 장점 및 사용 이유

배열을 이용해서 최솟값이나 최댓값을 찾기 위해서는 O(n)만큼 시간이 걸린다. 하지만 힙을 사용하게 되면 O(logn)만큼만 소요되므로 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다. 그래서 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 알고리즘 등에 활용된다. (우선순위 큐는 다음에 자세히 다루도록 하겠다.)