개발 기초/자료구조

[자료구조] 힙(heap)의 개념 및 Python heapq 라이브러리 정리

숩니따 2024. 1. 13. 03:23

전반적인 개념

들어가기 전

자료 구조

  • 스택(Stack)
    • 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 선형 자료구조
    • 마지막에 삽입한 자료를 가장 먼저 꺼내는 후입선출 구조
  • 큐(Queue)
    • 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
    • 먼저 삽입한 자료를 가장 먼저 꺼내는 선입선출 구조
  • 우선순위 큐(Priority Queue)
    • 우선순위 개념을 큐(Queue)에 도입한 자료 구조
    • 배열, 연결리스트, 힙을 통해서 구현 가능
    • 활용
      • Dijkstra’s Algorithm
      • A* Algorithm
      • Heap sort
      • Huffman coding

정의

힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 하여 우선순위큐를 위하여 만들어진 자료구조

힙 트리는 중복된 값을 허용

종류

이는 힙의 불변성을 어떤 식으로 유지하느냐 에 따라 종류가 나뉨

최대 힙

부모 노드 키 값이 자식 노드 키 값보다 크거나 같은 완전이진트리

최소 힙

부모 노드 키 값이 자식 노드 키 값보다 작거나 같은 완전이진트리

파이썬 heapq 모듈

공식 문서

힙은 모든 부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리로 이 구현에서 모든 k에 대해 heaqp[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]인 배열을 사용합니다.

비교를 위해서 존재하지 않는 요소는 무한으로 간주하고, 가장 작은 요소는 항상 루트인 heap[0] 입니다.

관련 메서드

heapq.heapush(heap, item)

힙의 불변성 유지하면서 item 값 힙으로 푸시

heapq.heappop(heap)

힙의 불변성을 유지하면서 item 값 힙에서 가장 작은 항목을 팝하고 반환

단, 비어있으면 IndexError 발생하고 팝하지 않고 가장 작은 항목에 접근하려면 루트인 heap[0]을 사용

heapq.heappushpop(heap, item)

힙에 item을 푸시한 다음 heap에서 가장 작은 항목을 팝하고 반환

heappush, heappop을 별도로 호출하는 것보다 효율적으로 움직이기 때문에 동시에 필요한 경우 이것을 쓰는 것이 효과적

heapq.**heapreplace**(heap, item)

힙에서 가장 작은 항목을 팝하고 반환하며, 새로운 item도 푸시

heappush, heappop을 별도로 호출하는 것보다 효율적으로 움직이기 때문에 동시에 필요한 경우 이것을 쓰는 것이 효과적

단, heappushpop과 다르게 팝을 먼저하고 푸시가 이루어지므로 비어있으면 IndexError 발생

heapq.heapify(x)

배열(리스트) x를 힙으로 변환

heapq.merge(*iterables, key=None, reverse=False*)*

여러 정렬된 배열(리스트)을 단일 정렬된 출력으로 병합하는데, 이때 여러 iterable한 값(ex. 리스트)이 정렬되어 있다고 가정

  • key는 각 입력 요소에서 비교 키를 추출하는데 사용되는 단일 인자 키 함수 (기본은 None)
import heapq

words1 = [(1, 'apple'), (3, 'plum')]
words2 = [(2, 'banana'), (4, 'grape')]

merge_result = heapq.merge(words1, words2, key=lambda x: x[1])

result = []

for word in merge_result:
    result.append(word)

print(result)

>>> [(1, 'apple'), (2, 'banana'), (4, 'grape'), (3, 'plum')]
  • reverse는 각 비교가 반대로 된 것처럼 입력 요소 병합 (기본은 False) True로 하면 기본으로 두 배열 요소는 유지하고 전체 병합을 결과(배열)를 내림차순으로 정렬
import heapq

numbers1 = [1, 4, 6, 8]
numbers2 = [2, 3, 7, 9]
numbers3 = [3, 5, 6, 10]

merge_result = heapq.merge(numbers1, numbers2, numbers3, reverse=True)

result = []

for number in merge_result :
    result.append(number)

print(result)

>>> [3, 5, 6, 10, 2, 3, 7, 9, 1, 4, 6, 8]

heapq.nlargest(n, iterable, key=None)

iterable에 정의된 리스트와 같은 데이터 집합에서 n개의 가장 큰 요소로 구성된 리스트를 반환

  • key는 Iterable의 각 요소에서 비교 키를 추출하는 데 사용되는 단일 인자 함수 지정 ex. key=str.lower

heapq.**nsmallest**(n, iterable, key=None)

iterable에 정의된 리스트와 같은 데이터 집합에서 n개의 가장 wkrdms 요소로 구성된 리스트를 반환

  • key는 Iterable의 각 요소에서 비교 키를 추출하는 데 사용되는 단일 인자 함수 지정 ex. key=str.lower

메서드 참고

※ nlargest, nsmallest 메서드는 n이 작은 경우 효과적으로 동작하고 값이 크면 sorted() 기능을 사용하는 것이 더 효율적이며 n==1일 때는 min(), max()를 사용하는 것이 더 효율적