[Data Structure] 힙(Heap)

본 포스트는 힙(Heap)에 대해 공부한 내용을 정리한 것입니다.

 

힙(Heap)은 이진 트리(Binary Tree) 기반의 자료구조로, 최대값 또는 최소값을 빠르게 찾는 연산에 유리합니다.

 

이진 트리에 대해 더 자세한 내용을 알고 싶으시다면, 아래 포스트를 참고해주세요~

[Data Structure] 이진 트리 (Binary Tree)

[Data Structure] 이진 트리 (Binary Tree)

 

그럼 본격적으로 힙에 대해 알아보도록 하겠습니다.

---

힙의 장단점

장점

1. 효율적인 삽입 및 삭제: 힙에서의 삽입과 삭제 연산은 O(log n)의 시간 복잡도를 가지므로, 대규모 데이터에서 빠른 연산이 가능합니다.
2. 최대값 또는 최소값을 빠르게 찾을 수 있음: 힙의 루트 노드는 항상 최대값 또는 최소값을 가지므로, 해당 값의 접근이 O(1) 시간 내에 가능합니다.
3. 우선순위 큐로의 활용: 힙은 우선순위 큐의 구현에 적합하며, 이를 통해 다양한 알고리즘(예: 다익스트라 알고리즘, 프림 알고리즘 등)에서 효율적으로 사용됩니다.

단점

1. 정렬되지 않은 상태: 힙은 최대값이나 최소값을 빠르게 찾을 수 있지만, 정렬된 구조는 아니기 때문에, 힙에서 정렬된 데이터를 얻기 위해서는 추가적인 연산이 필요합니다.
2. 일반적인 트리보다 복잡한 구현: 힙은 일반적인 이진 트리보다 구현이 다소 복잡합니다.

---

힙의 종류

힙은 크게 두 가지 종류가 있습니다.

 

1. 최대 힙(Max Heap)

• 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
• 부모 노드의 키 값 > 자식 노드의 키 값
• 루트 노드 : 키 값이 가장 큰 노드 

2. 최소 힙(Min Heap)

• 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
• 부모 노드의 키 값 < 자식 노드의 키 값
• 루트 노드 : 키 값이 가장 작은 노드

---

최대 힙(Max Heap) 구현

입력

7
20 15 19 4 13 11 17

 

코드 (최대 힙)

# 최대힙
def enq(n):
    global last
    last += 1   # 마지막 노드 추가(완전이진트리 유지)
    h[last] = n # 마지막 노드에 데이터 삽입
    c = last    # 부모>자식 비교를 위해
    p = c//2    # 부모번호 계산
    while p >= 1 and h[p] < h[c]:   # 부모가 있는데, 더 작으면
        h[p], h[c] = h[c], h[p]  # 교환
        c = p
        p = c//2


def deq():
    global last
    tmp = h[1]   # 루트의 키값 보관
    h[1] = h[last]
    last -= 1
    p = 1           # 새로 옮긴 루트
    c = p*2
    while c <= last:  # 자식이 있으면
        if c+1 <= last and h[c] < h[c+1]: # 오른쪽자식이 있고 더 크면
            c += 1
        if h[p] < h[c]:
            h[p], h[c] = h[c], h[p]
            p = c
            c = p*2
        else:
            break
    return tmp


N = int(input())          # 필요한 노드 수
arr = list(map(int, input().split()))

h = [0]*(N+1)   # 최대힙
last = 0        # 힙의 마지막 노드 번호

for num in arr:
    enq(num)

print(h)

while last > 0:
    print(deq(), end=' ')

 

결과

[0, 20, 15, 19, 4, 13, 11, 17]
20 19 17 15 13 11 4

---

최소 힙(Min Heap) 구현

입력

7
20 15 19 4 13 11 17

 

코드 (최소 힙)

# 최소힙
def enq(n):
    global last
    last += 1   # 마지막 노드 추가(완전이진트리 유지)
    h[last] = n # 마지막 노드에 데이터 삽입
    c = last    # 부모>자식 비교를 위해
    p = c//2    # 부모번호 계산
    while p >= 1 and h[p] > h[c]:   # 부모가 있는데, 더 크면
        h[p], h[c] = h[c], h[p]  # 교환
        c = p
        p = c//2


def deq():
    global last
    tmp = h[1]   # 루트의 키값 보관
    h[1] = h[last]
    last -= 1
    p = 1           # 새로 옮긴 루트
    c = p*2
    while c <= last:  # 자식이 있으면
        if c+1 <= last and h[c] > h[c+1]:  # 오른쪽자식이 있고 더 작으면
            c += 1
        if h[p] > h[c]:
            h[p], h[c] = h[c], h[p]
            p = c
            c = p*2
        else:
            break
    return tmp


N = int(input())          # 필요한 노드 수
arr = list(map(int, input().split()))

h = [0]*(N+1)   # 최대힙
last = 0        # 힙의 마지막 노드 번호

for num in arr:
    enq(num)

print(h)

while last > 0:
    print(deq(), end=' ')

 

결과

[0, 4, 13, 11, 20, 15, 19, 17]
4 11 13 15 17 19 20

---

heapq 라이브러리와 메서드 설명

Python에서는 'heapq' 라는 최소 힙(Min Heap) 기능을 가진 라이브러리를 제공하고 있습니다.

Python의 리스트를 이용해 힙 자료구조를 구현하며, 다양한 힙 관련 연산을 제공합니다.

주요 메서드는 다음과 같습니다.

• heapq.heappush(heap, item) : 힙에 새로운 요소 추가  
  • 시간복잡도 : O(log n)
• heapq.heappop(heap) : 힙에서 가장 작은 요소 제거 및 반환
  • 시간복잡도 : O(log n)
• heapq.heappushpop(heap, item) : 힙에 새로운 요소 추가한 후, 그 요소와 기존 최소값 중 더 작은 값을 제거하고 반환
  • 시간복잡도 : O(log n)
• heapq.heapreplace(heap, item) : 힙의 최소값을 제거하고, 새로운 요소 추가
  • 시간복잡도 : O(log n)
• heapq.heapify(x) : 리스트를 힙 구조로 변환
  • 시간복잡도 : O(n)
• heapq.nlargest(k, iterable) : n개의 요소로 구성된 iterable에서 k개의 가장 큰 요소 반환
  • 시간복잡도 : O(n log k)
• heapq.nsmallest(k, iterable) : n개의 요소로 구성된 iterable에서 k개의 가장 작은 요소 반환
  • 시간복잡도 : O(n log k)

 

heapq 라이브러리에는 보시다시피 여러가지 메서드가 포함되어 있습니다.

그러나, 자주 사용되는 것은 heappush, heappop 두 가지 입니다.

 

특히, nlargest, nsmallest의 경우, 정말 왠만해서는 잘 사용하지 않습니다.

그 이유는 아래와 같습니다.

nlargest, nsmallest는 리스트 요소를 힙 트리 구조로 만든 후 반환하기 때문에, n이 1이라면 min()이나 max()를 사용하는 것이, n이 리스트의 길이와 비슷하거나 같다면 sorted를 사용한 후 slicing을 사용하는 것이 낫습니다.

---

heapq 라이브러리 활용

입력

7
20 15 19 4 13 11 17

 

코드

from heapq import heappush, heappop

N = int(input())          # 필요한 노드 수
arr = list(map(int, input().split()))

heap = []  # 최대힙을 구현하기 위한 리스트

# 최소힙 ( 기본 )
for num in arr:
    heappush(heap, num)

print([x for x in heap])  # 힙의 내부 상태를 출력

while heap:
    print(heappop(heap), end=' ')

print('\n------------------------------------')

# 최대힙
# 삽입 시 음수로 곱하여 저장 (제일 큰 수가 제일 작아짐)
# 삭제 후 음수값을 곱하여 출력 (다시 원래 수로 복구하여 출력)
for num in arr:
    heappush(heap, -num)

print([-x for x in heap])  # 힙의 내부 상태를 출력 (음수로 저장된 상태)

while heap:
    print(-heappop(heap), end=' ')

 

결과

[4, 13, 11, 20, 15, 19, 17]
4 11 13 15 17 19 20
------------------------------------
[20, 15, 19, 4, 13, 11, 17]
20 19 17 15 13 11 4