[python] python 의 heapq라이브러리 사용법

python에는 heap트리를 구현하는 표준 라이브러리 heapq라는 라이브러리가 있다.

만약 heap 트리를 아직 모른다면 아래 링크를 보는 것을 추천합니다.

[자료구조] 힙트리의 정의와 구현 (Java)

[자료구조] 힙트리의 정의 와 구현 (Java)

 

heap트리 import

import heapq

heapq 특징

• 요소는 0부터 센다.
• 비교를 위해, 존재하지 않는 요소는 무한으로 간주.
• 최소 힙(Min heap)을 디폴트로 가진다는 점
  • 즉, heap[0]이 리스트 중 제일 작은 값

heap을 만들려면?

• [ ]로 초기화된 리스트를 사용하거나.
• 함수 heapify()를 통해 값이 들어 있는 리스트를 힙으로 변환할 수 있다.

[ ]로 초기화된 리스트를 사용

import heapq

li = []

heapq.heappush(li,10)
heapq.heappush(li,11)
heapq.heappush(li,3)
heapq.heappush(li,1)
heapq.heappush(li,4)
heapq.heappush(li,5)

print(li)

>>[1, 3, 5, 11, 4, 10]

heapify(iterable): 주어진 리스트를 힙으로 변환

import heapq

li = [1,5,73,0,2,4,13]

heapq.heapify(li)
print(li)

[0, 1, 4, 5, 2, 73, 13]

heap 삽입 삭제 연산

heappush(heap, item): 원소를 힙에 추가

import heapq

li = []

heapq.heappush(li,10)
heapq.heappush(li,11)
heapq.heappush(li,3)
heapq.heappush(li,1)
heapq.heappush(li,4)
heapq.heappush(li,5)

print(li)

heappop(heap): 힙에서 가장 작은 원소를 제거하고 반환

import heapq

li = []

heapq.heappush(li,10)
heapq.heappush(li,11)
heapq.heappush(li,3)
heapq.heappush(li,1)
heapq.heappush(li,4)
heapq.heappush(li,5)

for i in range(len(li)):
    print(heapq.heappop(li),end = " ")

1 3 4 5 10 11

max heap 사용하는 법

• 삽입 삭제 할 때 - 부호를 사용하는 것
• 이유는 디폴트가 최소힙이기 때문에 제일 작은 원소가 부모노드로 가는 특성이 있다.
• 하지만 -부호를 붙이면 1 3 이 -3 -1처럼 순서가 바뀐다.
• 그래서 최대힙을 사용하기 위해 - 를 붙인다.

import heapq

li = []

heapq.heappush(li,-10)
heapq.heappush(li,-11)
heapq.heappush(li,-3)
heapq.heappush(li,-1)
heapq.heappush(li,-4)
heapq.heappush(li,-5)

for i in range(len(li)):
    print(-heapq.heappop(li),end = " ")

nlargest,nsmallest

• 주어진 iterable에서 가장 큰 or 가장 작은 n개의 원소를 리스트로 반환
• 꼭 parameter로 오는 iterable이 heap배열이 아니어도 됨
• 내부적으로 heap배열로 변환 후 가장 크거나 작은 원소를 추출함
• 수행시간 : O(N log K) n은 iterable의 길이 K는 찾고자 하는 n의 크기

nlargest(n, iterable)

• heapq.nlargest(n, iterable) 함수는 주어진 iterable에서 가장 큰 n개의 원소를 찾아 리스트로 반환

import heapq

li = [1,25,6,5,1234,64]

print(heapq.nlargest(5,li))

nsmallest(n, iterable)

• heapq.nsmallest(n, iterable) 함수는 주어진 iterable에서 가장 작은 n개의 원소를 찾아 리스트로 반환

import heapq

li = [1,25,6,5,1234,64]

print(heapq.nsmallest(3,li))

정렬하기

• 오름차순

import heapq

li = [1,25,6,5,1234,64]

print(heapq.nsmallest(len(li),li))

• 내림차순

import heapq

li = [1,25,6,5,1234,64]

print(heapq.nlargest(len(li),li))