[Python] heapq

2373 ワード
python 白駿 アルゴリズム#アルゴリズム# テキストリンク

heapデータ構造

     1  ---> root
   /   \
  3     5
 / \   /
4   8 7
hipは完全なバイナリツリーデータ構造であり、hipは常にルートノードを削除します.
Pythonはheapqモジュールをインポートでき、heapqは最小スタック(minheap)データ構造を提供する.

モジュールのインポート

import heapq

お尻を使う

1. 빈 리스트를 생성하여 힙처럼 다루는 방법

heap = []
heapq.heappush(heap, 4) # 힙에 원소 추가하는 함수
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)
print(heap)
[1, 3, 7, 4]	# 실행 결과
heappush()関数を使用してhipに要素を追加できます.
2. 기존에 있던 리스트를 Heapify를 이용해 heap으로 만드는 방법

heap = [3, 4, 7, 2, 1]
heapq.heapify(heap)
print(heap)
[1, 2, 7, 3, 4] # 실행 결과
heapify()関数を使用すると、リストの要素がhip構造に基づいて再配置されます.
3. 힙에서 원소 삭제

heap = [1, 2, 7, 3, 4]
print(heapq.heappop(heap))
print(heap)
1				# 실행 결과
[2, 3, 7, 4]
heapppop()関数を使用して要素を削除し、最小の要素を削除して戻ることができます.

さいだいヒープ


heapqモジュールは最小ヒープ(mini heap)を基準としているので、最大ヒープ(max heap)を使用するには、すべての値に-を付けて、最大値を最小値にすることができます.
nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heapq.heappop(heap)[1])  # index 1
8		# 실행 결과
7		# 최대 힙 구조로 큰 값부터 출력됨
5
4
3
1

例



最小の2つの数を加えて、もう1つの値を加えて、加算を続けます.
from sys import stdin
import heapq

n = int(stdin.readline().rstrip('\n'))
data = []
for _ in range(n):
    data.append(int(stdin.readline().rstrip('\n')))
heapq.heapify(data)
ans = 0

while len(data) != 1:
    num1 = heapq.heappop(data)
    num2 = heapq.heappop(data)
    sum = num1 + num2
    ans += sum
    heapq.heappush(data, sum)

print(ans)
すべての入力値をdataというリストに入れ、heap構造に変換します.
次に加えて、最小の数字を減算し、加えて、和の値だけデータに再入れます.
出典:heapqモジュールの使い方、データ構造でーたこうぞう:優先キューゆうせんキュー
[Baekjoon] 1167. 木の直径[G 3]
遡及法によるサブセットと問題の解決