優先順位キューと臀部


優先度キューには、各アイテムに関連付けられた優先度があります.優先キューはhipを使用して実装されます.
お尻
これは、最高価格と最高価格を迅速に検索するために設計されたデータ構造です.
したがって、リスト内の最小または最大要素に再アクセスするプログラムは非常に役立ちます.시간복잡도 : O(log n)なぜ
  • ヒップを使うのか
    -配列にデータを入れ、最大/最小値を検索すると、時間の複雑さはO(n)になります.
  • hipにデータを入れて最大/最小値を求めるとO(logn)になります
  • 1-1. heapqモジュール
    リストを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')