📖Heapq

파이썬의 리스트를 최소 힙처럼 다룰 수 있도록 하는 모듈

import heapq
 
hq = []
heapq.heapify(hq) # 기존 list를 Min Heap으로 변환

• heapq는 생성하는 것이 아니라 일반 리스트를 이용
• 우선순위 큐 구현에 사용
• PriorityQueue 라이브러리보다 빠름
• default는 최소 힙

heapq를 Max Heap으로 만드려면?

1. v를 -v의 형태로 추가
2. v를 (-v, v)의 tuple 형태로 추가

📖삽입/삭제 함수

• O(log n)의 시간 복잡도를 가짐

📎heappush(list, v)

list에 v를 추가하는 함수

heapq.heappush(hp, v) # list에 Min Heap 기준으로 v값 추가

📎heappop(list)

최솟값(Min Heap 기준)을 삭제 후 return하는 함수

heapq.heappop(hp) # list에서 Min Heap 기준으로 값 삭제 후 return

heapq.heappush()로 데이터를 넣는다고 오름차순 정렬이 되지 않음

heapq.heappush()로 넣어준 데이터를 heapq.heappop()을 통해 꺼내는 과정에서 데이터가 정렬 ( ∵ heapq.heappop()을 호출하면 이진 트리의 재배치를 통해 매번 새로운 최솟값을 인덱스 0에 위치시킴)
🔖n번째로 작은 값에 접근하기 위해서는? hq[1]로 접근하는 것이 아님

1. heapq.heappop()으로 n-1개의 작은 값 삭제 → hq[0]에 접근해 n번째로 작은 값 접근
2. heapq.nsmallest(n, list)로 n개의 작은 값 리스트 만든 후 가장 마지막 값(hq[-1]) 접근

📖최댓값/최솟값 찾는 함수

📎최솟값/최댓값

heapq에서는 항상 0번째 값이 최솟값 (default인 Min heap 기준)

nums = [5, 4, 3, 2, 1]
heapq.heapify(nums)
 
nums[0] # 1 , 최솟값

• Max Heap으로 만들면 0번째 값이 항상 최댓값

📎nlargest(n, list, key)

list에서 n개의 가장 큰 요소들을 찾아 리스트로 return하는 함수

heapq.nlargest(n, list)

• key는 생략 가능
• key에는 가장 큰의 정의를 할 수 있음 (lambda 같은 함수식으로)

📎nsmallest(n, list, key)

list에서 n개의 가장 작은 요소들을 찾아 리스트로 return하는 함수

heapq.nsmallest(n, list)

• key는 생략 가능
• key에는 가장 작은의 정의를 할 수 있음 (lambda 같은 함수식으로)