Hyem.log

[Algorithm] 힙(Heap)

October 24, 2021

힙 (Heap) 자료구조

최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조

  • 완전 이진트리 형태임

    • 이진트리 : 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조
    • 완전 이진트리 : 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 왼쪽부터 채워져있다

  • 부모 노드와 자식 노드 사이에는 대소관계가 성립한다.

    • 부모 노드가 항상 자식 노드보다 큼 : 최대 힙
    • 부모 노드가 항상 자식 노드보다 작음 : 최소 힙
  • 대소관계는 오직 부모노드와 자식노드 간에만 성립하며, 형제 노드 사이에는 대소관계가 정해지지 않는다.

따라서 힙 구조에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 Root에 오게 되는 특징이 있으며, 이를 이용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

img

[이미지 출처] 위키백과 - 최대 힙 예시

파이썬 heapq 모듈

파이썬 내장 모듈로, 일반 리스트를 최소 힙처럼 다룰 수 있게 해줌

1) heapq 모듈 함수

✅ 모듈 임포트

import heapq

✅ 원소 추가 : heapq.heappush()

heap = []

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

✅ 원소 삭제 (최솟값 추출) : heapq.heappop()

heap = [1, 3, 7, 4]
print(heapq.heappop(heap)) # 1
print(heap)  # [3, 7, 4]

✅ 리스트를 힙으로 변환 : heapq.heapify()

nums = [4,5,7,9,2,3,1]
heapq.heapify(nums)
print(nums)  # [1, 2, 3, 9, 5, 4, 7]

✅ 첫번째 ~ n번째 큰 값 / 작은 값 찾기 : heapq.nlargest() / heapq.nsmallest()

heap = [4,5,7,9,2,3,1]
print(heapq.nlargest(3, heap))  # [9, 7, 5]
print(heapq.nsmallest(2, heap))  # [1, 2]

2) 힙 자료구조 응용

✅ 최대 힙 만들기

nums = [4,5,7,9,2,3,1]
heap = []

for n in nums:
    heapq.heappush(heap, (-n, n))  
    # 힙에 튜플을 저장하면 튜플의 첫 번째 원소를 기준으로 힙이 구성됨. 
    # 즉 -n은 최소 힙이 아니라 최대 힙을 구성하기 위한 우선순위 표시를 위한 것

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

✅ 힙 정렬 : 루트에 항상 최솟값이 온다는 힙 자료구조의 성질을 이용한 정렬 방법

시간복잡도 : O(nlogn)

  • 원소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간 logn
  • 원소 개수 n개를 다 정비하면 되므로 총 nlogn
def heap_sort(nums):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)

    sorted_nums = []
    while heap:
        sorted_nums.append(heapq.heappop(heap))  # 값이 작은 순으로 차례대로 들어가게 됨

    return sorted_nums

print(heap_sort([4,5,7,9,2,3,1]))  # [1, 2, 3, 4, 5, 7, 9]
Written by@[hyem]
Hyem's Dev Note

GitHub