優先順位キューと臀部
優先度キューには、各アイテムに関連付けられた優先度があります.優先キューはhipを使用して実装されます.
お尻
これは、最高価格と最高価格を迅速に検索するために設計されたデータ構造です.
したがって、リスト内の最小または最大要素に再アクセスするプログラムは非常に役立ちます.ヒップを使うのか
-配列にデータを入れ、最大/最小値を検索すると、時間の複雑さはO(n)になります. hipにデータを入れて最大/最小値を求めるとO(logn)になります
1-1. heapqモジュール
リストをhipに変換
最も優先度の高いデータ構造.
お尻
これは、最高価格と最高価格を迅速に検索するために設計されたデータ構造です.
したがって、リスト内の最小または最大要素に再アクセスするプログラムは非常に役立ちます.
시간복잡도 : O(log n)
なぜ-配列にデータを入れ、最大/最小値を検索すると、時間の複雑さはO(n)になります.
リストをhipに変換
import heapq
list1 = [4, 6, 8, 1]
heapq.heapify(list1)
print(list1)
> [1, 4, 8, 6]
プロジェクトにhip>heapqを挿入します.heappush(heap, item)import heapq
h = []
heapq.heappush(h, (1, 'food'))
heapq.heappush(h, (2, 'fruit'))
heapq.heappush(h, (1, 'drink'))
print(h)
> [(1, 'drink'), (2, 'fruit'), (1, 'food')]
お尻から最小のアイテムを除去し、結果を返します.import heapq
list1 = [1,3,4,6]
heapq.heappop(list1)
print(list1)
> [3, 4, 6]
複数のリストの値をイテレーションに戻すfor x in heapq.merge([1,4,7],[2,9,10]):
print(x)
> 1
> 2
> 4
> 7
> 9
> 10
優先キュー最も優先度の高いデータ構造.
import heapq
hq = []
heapq.heappush(hq, (30,'red'))
heapq.heappush(hq, (15,'blue'))
heapq.heappush(hq, (19,'white'))
print(hq)
> [(15, 'blue'), (30, 'red'), (19, 'white')]
first = heapq.heappop(hq)
print(first)
> (15, 'blue')
print(hq)
> [(19, 'white'), (30, 'red')]
second = heapq.heappop(hq)
print(second)
> (19, 'white')
Reference
この問題について(優先順位キューと臀部), 我々は、より多くの情報をここで見つけました https://velog.io/@may_soouu/우선순위-큐와-힙テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol