[파이썬] Heapq 알고리즘

힙 (heap)

사진 출처 - 나무위키

부모 노드가 자식보다 작거나 같은 값을 가진 이진 트리. 모든 k에 대해 heap[k] <= heap[2*k+ 1] 와 heap[k] <= heap[2*k+2]를 만족한다.

가장 작은 요소는 항상 heap[0]이며, 힙을 만들기 위해서는 리스트를 사용하거나 heapify() 함수를 통해 값이 들어 있는 리스트를 힙으로 바꾸면 된다.

함수

heapq.heappush(heap, item)

힙 불변성 유지 + item 값을 heap 에 푸쉬한다.

heapq.heappop(heap)

힙 불변성을 유지 + heap에서 가장 작은 항목을 pop한다.
pop()하지 않고 가장 작은 항목에 엑세스하려면 heap[0]를 사용할 것.

heapq.heappushpop(heap, item)

힙에 item 푸쉬 -> heap에서 가장 작은 항목을 pop.
두 함수를 따로 쓴 것보다는 효율적으로 진행된다.

heapq.heapify(x)

리스트 x를 힙으로 변환시킨다.

heapq.heapreplace(heap, item)

heap에서 가장 작은 항목 pop -> 새로운 item 푸쉬
힙 크기는 변경되지 않는다.
반환된 값이 추가된 item 값보다 클 수 있는데, 이게 의도와 맞지 않다면 heappushpop()을 권장한다.

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

• 여러 정렬된 입력을 단일 정렬된 출력으로 병합한다.
• 이터러블을 반환하고, 데이터를 한 번에 메모리로 가져오지 않으며, 이미 최소에서 최대로 정렬됐다고 가정한다.
• key는 각 입력 요소에서 비교 키를 추출하는 데 사용되는 단일 인자의 키 함수를 지정한다. 기본값은 None이다.

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

iterable에 의해 정의된 데이터 집합에서 n개의 가장 큰 요소로 구성된 리스트를 반환한다. key가 제공되면 각 요소에서 비교 키를 추출하는 데 사용되는 단일 인자 함수를 지정한다. 뭐라는거야???
ex) key = str.lower 이라고 한다면 sorted(iterable, key = key, reverse = True)[:n]와 동일

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

iterable에 의해 정의된 데이터 집합에서 n개의 가장 작은 요소로 구성된 리스트 반환.

마지막 두 함수는 n 값이 작을 때 잘 동작한다. 값이 크다면 sorted()를 쓰는 게 더 효율적이다.

우울하네요 다시 공부해서 돌아오겠습니다.....................

최소 힙

백준 1927번 :

import heapq
import sys

size = int(sys.stdin.readline())
nums = []
myHeap = []

for _ in range(size):
    nums = int(sys.stdin.readline())

    if (nums > 0):
        heapq.heappush(myHeap, nums)
    elif (len(myHeap) == 0):
        print(heapq.heappushpop(myHeap, 0))
    else:
        print(heapq.heappop(myHeap))

최대 힙

백준 11279번

import sys
import heapq

size = int(sys.stdin.readline())
maxHeap = []
for _ in range(size):
    nums = int(sys.stdin.readline())

    if (nums != 0):
        heapq.heappush(maxHeap, (-1) * nums)
    else:
        try:
            print((-1) * heapq.heappop(maxHeap))
        except:
            print(0)

heappop() 함수는 해당 힙에서 가장 작은 원소값을 반환한다. 따라서 가장 큰 원소를 pop 하기 위해서는 사용자가 입력한 숫자에 -1을 곱해서 값을 저장하고, 출력할 때는 다시 -1을 곱해서 출력하면 된다.

혹은 아래처럼 힙에다가 값을 저장할 때 (우선순위, 원소) 순으로 된 튜플 형태로 원소를 저장하면 된다. 아래 코드는 https://www.daleseo.com/python-heapq/ 이 글을 참고해서 작성했습니다.

import sys
import heapq

size = int(sys.stdin.readline())
maxHeap = []

for _ in range(size):
    nums = int(sys.stdin.readline())

    if (nums != 0):
        heapq.heappush(maxHeap, (-nums, nums))
    else:
        try:
            print(heapq.heappop(maxHeap)[1])
        except:
            print(0)