[자료구조] 힙(Heap) 에 대하여

힙이란?​

힙(Heap)이란, 완전 이진 트리에 있는 노드 중에서

키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조이다.

 

키 값이 가장 큰 노드를 찾기 위한 힙을 최대 힙(Max Heap)이라 하고,

키 값이 가장 작은 노드를 찾기 위한 힙을 최소 힙(Min Heap)이라고 한다.

 

아래 그림은 최대 힙과 최소 힙의 예시이다.

 

힙의 연산​

힙에는 새로운 원소를 추가하는 삽입 연산,

루트 노드에 있는 원소를 삭제하는 삭제 연산 두가지가 존재한다.

 

다만, 힙은 항상 부모노드를 최대 힙일 경우 최대, 최소 힙일 경우 최소로 유지해주어야 하는 특성이 있다.

• 최대 힙 : 부모노드의 키 값 >= 자식노드의 키 값
• 최소 힙 : 부모노드의 키 값 <= 자식노드의 키 값

이제 각각의 연산의 과정과 시간복잡도에 대해 알아보자.

 

힙의 삽입 연산​

간단하게 먼저 말로 순서를 설명해 보자면 다음과 같다.

1. 새로운 노드를 힙의 마지막 노드에 삽입한다.
2. 새로운 노드를 부모 노드들과 교환해 힙의 성질을 만족시킨다.

그림으로 보면 아래와 같은 과정을 거친다. (최대 힙의 삽입 과정)

 

 

생각해 볼 것

Q: 루트 노드까지 올라왔을 때 마지막에 반대편 자식노드와 크기를 비교해서 위치를 재조정 해주어야 하지 않나요?

A: 이미 20보다 큰 23과 비교해서 교환이 된 상태이기 때문에 20보다 작은 왼쪽 노드와 다시 한번 비교를 해주지 않아도 된다.

 

힙의 삭제 연산​

힙의 삭제 연산은 언제나 루트 노드에 있는 원소를 삭제하여 반환한다.

따라서 루트 노드를 삭제하고 다시 트리를 힙의 조건으로 유지시켜주어야 한다.

 

과정은 다음과 같다.

1. 힙의 루트 노드를 삭제 후 반환
2. 마지막 노드를 루트 노드로 이동
3. 힙의 조건에 맞게 트리를 재 조정

그림으로 보면 아래와 같은 과정을 거친다. (최대 힙의 삭제 과정)

 

주의!

삭제 연산에서 트리를 재 조정할 때, 최대 힙일 경우 더 큰 자식과 크기를 비교한다.
반대로, 최소 힙일 경우에는 더 작은 자식과 크기를 비교한다.

 

! 생각해 볼 것

Q: 마지막 노드를 위로 올리는 과정에서, 마지막 노드를 탐색할 때도 트리의 탐색 과정을 따르나요?

A: 이 질문은 힙을 어떻게 구현하느냐에 따라 답이 다릅니다.
배열로 구현을 할 경우 인덱스로 빠르게 마지막 노드에 접근할 수 있지만,
단일 연결 리스트로 이진트리를 구현한다면, O(log N)의 시간으로 마지막 노드의 탐색 시간이 소요될 수 있습니다.

 

힙 연산의 시간복잡도​

삽입과 삭제 모두 힙의 높이(이진 트리의 높이)만큼 연산하는 경우가 최악의 경우 이므로,

힙의 높이가 무엇인지 안다면 그 시간복잡도를 알 수 있다.

 

완전 이진 트리의 모든 노드가 존재한다고 했을 때 높이를 h라고 하고 노드의 개수를 n이라고 하면 다음이 성립한다.

 

이는 등비수열의 합 공식에 의하여 다음과 같다.

 

즉,

위의 식에 양변에 로그를 취하면 다음과 같다.

 

따라서, 시간 복잡도는

O(h) = O(log2(n+1)-1) = O(log2n) 이다.

 

힙 사용 예시​

앞서 살펴본 바와 같이 힙은 최댓 값이나 최솟 값을 찾는데 사용된다.

또한 우선순위 큐를 구현할 때 가장 효율적인 자료구조가 heap이기도 하다.

 

마지막으로 힙 정렬을 만들 때 힙을 쓰기도하고, 무손실 압축 알고리즘인 허프만 코드도 힙의 구조를 기반으로 하고 있다.

 

힙 간략 코드​

C언어로 구현한 코드는 위키백과 수도코드와 C언어 코드를 참고하면 좋을 것 같다.

여기서는 python의 heapq 모듈 사용법을 설명해보려고 한다.

# heapq 모듈 선언
import heapq

# heap 배열 생성
heap = []

# 힙에 원소 추가
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

# 힙에 원소 삭제
heapq.heappop(heap) # 가장 작은 1이 삭제됨 ( 기본적으로 최소힙 )