[파이썬 개념]heapq

heapq 라이브러리를 이용해서 최소 힙(min heap: pop할 때 값이 가장 작은 데이터가 먼저 삭제) 구현 가능

원래 리스트를 힙으로 만들 때 heapq.heapify

heapq.heapify(a)
a[0]은 a 리스트의 최솟값

1. 최소 힙 by heapq

>>> import heapq
>>> a = []
>>> heapq.heappush(a,(0,1))
>>> a
[(0, 1)]
>>> heapq.heappush(a,(4,1))
>>> a
[(0, 1), (4, 1)]
>>> heapq.heappush(a,(2,1))
>>> a
[(0, 1), (4, 1), (2, 1)]
>>> print(heapq.heappop(a))
(0, 1)
>>> print(heapq.heappop(a))
(2, 1)

import heapq

# 오름차순 힙 정렬(= 최소 힙: 작은 데이터 부터 pop 됨)
def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result
result = heapsort([1,3,5,7,2,4,6,8,0])
print(result)

2. 최대 힙 by heapq

import heapq

# 내림차순 힙 정렬(Heap Sort)
def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h, -value) # value를 음수로 만들어서 추가
    print(h)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(-heapq.heappop(h))# pop한 값을 다시 음수화해서 result에 집어 넣기
    return result

result = heapsort([1,3,-5,7,2,4,6,8,0])
print(result)

자세한 설명
https://velog.io/@leese1016/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98week4#heapq-%EB%AA%A8%EB%93%88