힙(Heap)

최소 힙(Min Heap)과 최대 힙(Max Heap)이 있습니다.
다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 사용됩니다.

목차
1. 📌 힙이란?
2. 📌 힙의 구조, 동작 원리
3. 📌 파이썬 heapq 라이브러리
4. 📌 힙 자료구조의 활용

📌 힙이란?

• 완전 이진 트리의 일종
• 여러 개의 값들 중에서 최댓값, 최솟값을 빠르게 찾아내도록 만들어진 자료구조
• 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리
• 시간복잡도 : 삽입, 삭제 둘 다 O(logN)
  

📌 힙의 구현

• 보통 리스트(배열)에 저장한다.
• 구현을 쉽게 하기 위해서 첫 번째 인덱스인 0은 사용되지 않는다.
• 부모노드와 자식노드간의 관계
  • 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
  • 오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
  • 부모의 인덱스 = (자식의 인덱스) / 2

힙의 구조를 배열로 표현

힙의 삽입

힙의 제거

📌 파이썬에서 heapq 라이브러리로 구현

파이썬의 heapq 라이브러리는 최소 힙으로 구현되어 있습니다.

• 기존에 리스트 힙으로 변환 : heapify(heap) <시간복잡도 : O(N)>

import heapq

heap = [1,5,4,3,2]
heapq.heapify(heap) # 리스트 -> 힙
print(heap)
>> [1, 2, 4, 3, 5]

• 노드 추가 : heappush(heap, node)

import heapq

heap = [1,5,4,3,2]
heapq.heapify(heap)
heapq.heappush(heap, 6) # 노드 추가
print(heap)
>> [1, 2, 4, 3, 5, 6]

• 노드 삭제 : heappop(heap, node)

import heapq

heap = [1,5,4,3,2]
heapq.heapify(heap)
heapq.heappush(heap, 6) # 노드 추가
print(heapq.heappop(heap))
print(list)
>> 1
>> [2, 3, 4, 6, 5]

📌 힙 자료구조의 활용

최대 힙 만들기

• 파이썬의 라이브러리는 기본적으로 최소 힙 구조입니다.
• 이를 약간의 테크닉을 활용? 하여 최대 힙으로 만들 수 있는 방법이 2가지 있습니다.

1번째 방법: 우선 순위가 포함된 튜플 이용하기

import heapq

nums = [1,5,4,2,6,8]
heap = []

for num in nums:
    heapq.heappush(heap, (-num, num))

while heap:
    print(heapq.heappop(heap)[1])

2번째 방법: 입력과 출력을 할 때 부호를 바꿔주기

import heapq

nums = [1,5,4,2,6,8]
heap = []

for num in nums:
    heapq.heappush(heap, -num)

while heap:
    print(-heapq.heappop(heap))

힙을 활용해 리스트 정렬하기

• python에서 기본 라이브러리에서 사용하는 sort와 비슷한 성능을 가집니다.

import heapq

def heapsort(iterable, reverse = False): # 시간 복잡도 O(NlogN)
    if reverse: # reverse가 false이면 오름차순, true이면 내림차순 정렬
        sign = -1
    else:
        sign = 1
    heap = []
    result = []
    for value in iterable:
        heapq.heappush(heap, sign * value)

    for i in range(len(heap)):
        result.append(sign * heapq.heappop(heap))

    return result

리스트와 힙의 차이점

• 우선순위가 가장 높은 것을 삭제하고 싶을 때 리스트에서는 모든 원소를 확인해야 하므로 O(N)의 시간이 소요
• 힙에서는 삽입할 때 O(logN)이 소요되지만 우선순위가 가장 높은 것을 찾아야 하거나 삭제할 때 O(logN)이 소요되어 리스트보다 효율적이다.