[자료구조] 힙(Heap) 자료구조에 대해 알아보자!(+Python 구현)

📚 목차

1.  힙 자료구조
2.  힙 자료구조는 언제 사용할까?
3.  힙 자료구조의 종류
4.  힙 자료구조의 동작 과정(최소 힙)
    4.1.  데이터 삽입
    4.2.  데이터 삭제
5.  힙 자료구조 구현(Python)
    5.1.  heapq 셋업
    5.2.  힙 데이터 삽입(heappush)
    5.3.  힙 데이터 삭제(heappop)
    5.4.  리스트를 힙으로 변경(heapify)

1.  힙 자료구조

힙 자료구조는 가장 높은(혹은 가장 낮은) 우선순위(e.g., 최댓값, 최솟값)를 가지는 노드를 빠르게 찾아내기 위해 고안된 *완전 이진트리(Complete Binary Tree) 기반의 자료구조입니다. 따라서 가장 높은(또는 가장 낮은) 우선순위를 가지는 노드가 항상 루트 노드(root node)에 오는 게 특징입니다.

 

* 완전 이진 트리(Complete Binary Tree) 자료구조란?

완전 이진 트리란 각 노드가 최대 2개의 자식 노드를 갖는 트리 형태의 자료구조로서 마지막 레벨을 제외한 모든 노드는 완전히 채워져 있어야 합니다. 또한, 최하단 레벨의 노드는 좌측만 노드가 채워져 있거나 좌측과 우측 모두 채워져 있어야 하며, 노드를 삽입할 때는 최하단 좌측 노드부터 차례대로 삽입해야 합니다(그림 1 참고). 그림 1 우측 트리는 노드 12의 자식 노드가 우측에만 삽입되어 있기 때문에 완전 이진트리라고 할 수 없습니다.

 

그림 1. 완전 이진 트리 자료구조의 올바른 예시(좌측)와 올바르지 않은 예시(우측)

힙은 다음과 같은 속성이 있습니다.

• A가 B의 부모 노드(parent node)일 때 A 노드의 키(key) 값과 B 노드의 키 값에는 대소 관계가 성립한다.
• 키 값의 대소 관계는 반드시 부모-자식 노드 간에 성립하며, 형제 노드 간에는 성립하지 않는다.

2.  힙 자료구조는 언제 사용할까?

N개의 데이터가 저장된 리스트에서 최댓값 또는 최솟값을 탐색하려면 O(N) 만큼의 시간이 필요합니다. 반면 힙 자료구조는 O(logN) 만큼의 시간이 필요합니다. 따라서 최댓값이나 최솟값을 빠르게 탐색해야 하는 우선순위 큐, 최단 경로 알고리즘 등을 구현할 때 유용합니다.

3.  힙 자료구조의 종류

힙 자료구조의 종류는 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 총 2가지입니다. 최대 힙은 부모 노드의 key 값이 항상 자식 노드의 key 값보다 큰 경우이며, 반대로 최소 힙은 부모 노드의 key 값이 항상 자식 노드의 key 값보다 작은 경우입니다.

 

(1) 최대 힙: 부모 노드 Key > 자식 노드Key

(2) 최소 힙: 부모 노드 Key < 자식 노드Key

 

2가지 종류 중 주로 최소 힙이 사용됩니다. 그래서 최대 힙을 사용할 때에도 일부러 우선순위에 해당하는 값의 부호를 음수로(neagetive) 표현해 자료구조에 삽입한 후, 자료구조에서 데이터를 꺼낸 후 다시 음의 부호를 부여해 기존의 값으로 치환하는 방식을 사용하는 경우가 많습니다.

4.  힙 자료구조 동작 과정(최소 힙)

힙 자료구조는 크게 데이터 삽입과 삭제가 있습니다.  최소 힙을 중심으로 동작 과정을 살펴보겠습니다.

4.1.  힙 데이터 삽입

최소 힙 자료구조에서 데이터 삽입 동작 과정은 다음과 같습니다.

 

1️⃣  최하단 레벨의 좌측부터 순서대로 노드를 삽입합니다.

2️⃣  삽입한 노드의 key 값이 부모 노드의 key 값보다 작을 경우(최소 힙) 두 노드의 위치를 바꿉니다.

3️⃣  최소 힙 자료구조를 만족할 때까지 2️⃣ 과정을 반복합니다.

 

아래 그림 2 와 같은 힙 자료구조가 있을 때 데이터 3을 삽입해 보겠습니다.

 

그림 2. 힙 자료구조 예시1

 

항상 최하단 레벨의 좌측부터 순서대로 노드를 삽입해야 된다고 했습니다. 노드 12의 자식 노드 23이 최하단 레벨이며 좌측에 위치해 있습니다. 따라서 그림 3 과 같이 삽입할 노드는 노드 23의 우측에 삽입됩니다. 편의상 삽입한 노드는 파란색으로 표현하겠습니다.

 

그림 3. 최하단 레벨에 데이터 삽입

 

이제 삽입한 노드의 key 값과 부모 노드의 key 값을 비교합니다 (그림 4 참고). 편의상 key 값을 비교할 부모 노드는 녹색으로 표현하겠습니다. 노드 12는 노드 3보다 key 값이 크기 때문에 삽입된 데이터(자식 노드)와 부모 노드의 위치를 서로 바꿉니다.

 

그림 4. 부모-자식 노드 간의 key 값 비교1

 

노드 3은 다시 부모 노드인 노드 7과 key 값을 비교합니다. key 값이 노드 3이 작기 때문에 노드 7과 위치를 바꿉니다(그림 5 참고).

 

그림 5. 부모-자식 노드 간의 key 값 비교2

 

노드 3은 다시 부모 노드인 노드 5와 key 값을 비교합니다. key 값이 노드 3이 작기 때문에 노드 5와 위치를 바꿉니다(그림 6 참고).

 

그림 6. 부모-자식 노드 간의 key 값 비교3

 

이제 아래 그림 7 과 같이 최소 힙 자료구조가 만족된 것을 확인하실 수 있습니다.

 

그림 7. 최종 힙 자료 구조

4.2.  힙 데이터 삭제

최소 힙 자료구조에서 데이터 삭제 동작 과정은 다음과 같습니다.

 

1️⃣  최상단(루트) 노드를 추출합니다.

2️⃣  최하단 레벨의 우측 노드부터(없을 경우 좌측 노드) 루트 노드로 이동시킵니다.

3️⃣  이동한 노드의 key 값이 자식 노드의 key 값보다 클 경우(최소 힙) 두 노드의 위치를 바꿉니다.

4️⃣  최소 힙 자료구조를 만족할 때까지 3️⃣ 과정을 반복합니다.

 

아래 그림 8 과 같은 힙 자료구조가 있을 때 데이터를 삭제해 보는 동작 과정을 살펴보겠습니다.

 

그림 8. 힙 자료구조 예시2

 

먼저, 루트 노드인 노드 1을 추출합니다. 그리고 최하단 레벨의 우측 노드인 노드 12를 루트 노드로 이동시킵니다. 편의상 최하단 레벨의 우측 노드였던 노드를 파란색으로 표현하겠습니다(그림 9 참고).

 

그림 9. 루트 노드를 추출하고 최하단 레벨의 우측 노드를 루트 노드가 이동된 상태

 

이제 자식 노드와 key 값을 비교합니다. 편의상 key 값을 비교하는 자식 노드를 초록색으로 표현하겠습니다. 노드 12는 자식 노드인 노드 2보다 값이 크기 때문에 위치를 서로 변경합니다(그림 10 참고).

 

그림 10. 부모-자식 노드 간의 key 값 비교1

 

이제 노드 12와 자식 노드인 노드 5와 key 값을 비교합니다. 자식 노드 값이 더 작기 때문에 부모 노드 12와 위치를 서로 변경합니다(그림 11 참고).

 

 

그림 11. 부모-자식 노드 간의 key 값 비교2

 

마찬가지 방식으로 부모-자식 노드 간의 key 값을 비교합니다. 이번에는 부모 노드인 12가 자식 노드인 25보다 key 값이 작기 때문에 최소 힙 자료구조를 만족합니다(그림 12 참고). 따라서 더 이상 노드 간의 위치를 변경할 필요가 없습니다.

 

그림 12. 부모-자식 노드 간의 key 값 비교3

5.  힙 자료구조 구현(Python)

파이썬에 내장된 heapq 라이브러리를 사용하면 최소 힙 자료구조를 구현할 수 있습니다.

5.1.  heapq 셋업

import heapq

# 힙 생성
heap = []

먼저, heapq 라이브러리를 import 하고 힙 데이터를 저장할 리스트를 생성합니다.

5.2.  힙 데이터 삽입(heappush)

# 힙 이름과 추가할 원소를 각각 입력
heapq.heappush([힙 이름], [추가할 원소])

heappush 메소드를 활용하면 최소 힙 자료구조를 유지하면서 새로운 원소를 추가할 수 있습니다.

예시

# 힙 내 원소 할당
heapq.heappush(heap, '2')
heapq.heappush(heap, '5')
heapq.heappush(heap, '1')
heapq.heappush(heap, '3')
heapq.heappush(heap, '6')
heapq.heappush(heap, '4')

print(heap) # 결과: ['1', '3', '2', '5', '6', '4']

key 값에 상관없이 노드를 삽입해도 heapq 라이브러리는 최소 힙 자료구조를 유지하면서 데이터가 저장되는 것을 확인하실 수 있습니다.

5.3.  힙 데이터 삭제(heappop)

heapq.heappop([힙 이름])

heappop 메소드를 활용하면 최소 힙 자료구조를 유지하면서 우선순위가 가장 높은 원소를 추출합니다.

예시

print(heapq.heappop(heap)) # 결과: 1
print(heap) # 결과: ['2', '3', '4', '5', '6']

 

heappop 메서드를 통해 루트 노드인 1이 추출되어 이제 heap 자료구조 내 인덱스 0은 루트 노드인 1 바로 다음으로 큰 값인 2가 해당되는 것을 확인하실 수 있습니다.

5.4.  리스트를 힙으로 변경(heapify)

heapq.heapify([리스트 이름])

# 예시
list = [1, 3, 2, 5, 4]
heapq.heapify(list)

heapify 메서드를 활용하면 기존에 생성한 리스트를 힙 자료구조로 변경할 수 있습니다.

---

포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 감사드리겠습니다.

그럼 오늘도 즐거운 하루 보내시길 바랍니다 :)

고맙습니다.