heapq

---

heapq

deque처럼 deque객체를 생성하는 것이 아니라 list를 최소힙처럼 다룰 수 있도록 도와준다.

heqpq모듈을 통해 원소를 추가하거나 삭제하면 해당 리스트는 최소힙 성질을 가지게 된다.

• heappush: 첫번째 파라미터는 원소를 추가할 대상 리스트, 두번째 파라미터는 추가할 원소
• heappop: 파라미터로 넘겨 받은 리스트의 가장 작은 원소를 삭제, 리턴
  내부적으로 이진 트리에 원소를 추가, 삭제하므로 두 함수 모두 \(O(logn)\)의 시간 복잡도를 가진다.

In [1]:

# heapq를 이용한 힙정렬 구현
import heapq

def heapsort_min(arr):
    h = []
    result = []
    # 힙에 삽입
    for value in arr:
        heapq.heappush(h, value)
    # 힙에서 꺼내서 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

def heapsort_max(arr): # heapq 라이브러리는 최대힙을 제공하지 않음
    h = []
    result = []
    # 힙에 삽입
    for value in arr:
        heapq.heappush(h, -value)
    # 힙에서 꺼내서 담기
    for i in range(len(h)):
        result.append(-heapq.heappop(h))
    return result

arr = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
result = heapsort_min(arr)
print(result)
result = heapsort_max(arr)
print(result)

Out [1]:

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

• heapify: 이미 원소가 존재하는 리스트가 힙 구조에 맞게 재배치
  \(O(n)\)의 시간 복잡도를 가진다.

In [2]:

arr = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]

heapq.heapify(arr)
print(arr)

Out [2]:

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

• nsmallest, nlargest: 가장 작은 n개의 값, 가장 큰 n개의 값을 리스트로 반환

In [3]:

arr = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]

print('가장 작은 값 3개:', heapq.nsmallest(3, arr))
print('3번째 작은 값:', heapq.nsmallest(3, arr)[-1])

Out [3]:

가장 작은 값 3개: [0, 1, 2]
3번째 작은 값: 2

In [4]:

arr = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]

print('가장 큰 값 3개:', heapq.nlargest(3, arr))
print('3번째 큰 값:', heapq.nlargest(3, arr)[-1])

Out [4]:

가장 큰 값 3개: [9, 8, 7]
3번째 큰 값: 7

Reference

• DaleSeo : 파이썬의 heapq 모듈로 힙 자료구조 사용하기