パイソン 。
単純なヒープの作成
の heapify(反復可能) :- この関数は次の目的で使用されます。 イテラブルをヒープに変換する データ構造。つまり、ヒープ順に。
Python3
# importing 'heapq' to implement heap queue> import> heapq> # initializing list> li>=> [>5>,>7>,>9>,>1>,>3>]> # using heapify to convert list into heap> heapq.heapify(li)> # printing created heap> print> (>'The created heap is : '>,(>list>(li)))> |
>
>出力
The created heap is : [1, 3, 9, 7, 5]>
アイテムの追加とポップを効率的に行う
- heappush(heap, ele) : この関数は、引数で指定された要素をヒープに挿入するために使用されます。の ヒープ構造が維持されるように順序が調整されます。 heappop(heap) : この関数は、ヒープから最小の要素を削除して返すために使用されます。ヒープ構造が維持されるように順序が調整されます。
Python3
# importing 'heapq' to implement heap queue> import> heapq> # initializing list> li>=> [>5>,>7>,>9>,>1>,>3>]> # using heapify to convert list into heap> heapq.heapify(li)> # printing created heap> print>(>'The created heap is : '>, end>=>'')> print>(>list>(li))> # using heappush() to push elements into heap> # pushes 4> heapq.heappush(li,>4>)> # printing modified heap> print>(>'The modified heap after push is : '>, end>=>'')> print>(>list>(li))> # using heappop() to pop smallest element> print>(>'The popped and smallest element is : '>, end>=>'')> print>(heapq.heappop(li))> |
>
>出力
The created heap is : [1, 3, 9, 7, 5] The modified heap after push is : [1, 3, 4, 7, 5, 9] The popped and smallest element is : 1>
アペンディングとポップ 同時に
- heappushpop(heap, ele) :- この関数は、プッシュ操作とポップ操作の両方の機能を 1 つのステートメントに結合し、効率を高めます。この操作の後、ヒープの順序は維持されます。 heapreplace(heap, ele) :- この関数も 1 つのステートメント内で要素の挿入とポップを行いますが、上記の関数とは異なります。この場合、最初に要素がポップされ、次に要素がプッシュされます。つまり、プッシュされた値よりも大きな値を返すことができます。 heapreplace() は、 heappushpop() とは対照的に、プッシュされた要素に関係なく、元々ヒープ内にあった最小値を返します。
Python3
# importing 'heapq' to implement heap queue> import> heapq> # initializing list 1> li1>=> [>5>,>1>,>9>,>4>,>3>]> # initializing list 2> li2>=> [>5>,>7>,>9>,>4>,>3>]> # using heapify() to convert list into heap> heapq.heapify(li1)> heapq.heapify(li2)> # using heappushpop() to push and pop items simultaneously> # pops 2> print>(>'The popped item using heappushpop() is : '>, end>=>'')> print>(heapq.heappushpop(li1,>2>))> # using heapreplace() to push and pop items simultaneously> # pops 3> print>(>'The popped item using heapreplace() is : '>, end>=>'')> print>(heapq.heapreplace(li2,>2>))> |
>
>出力
The popped item using heappushpop() is : 1 The popped item using heapreplace() is : 3>
Python でヒープから最大要素と最小要素を見つける
- nlargest(k, iterable, key = fun) : この関数は、指定された反復可能オブジェクトから k 個の最大の要素を返し、指定されている場合はキーを満たすために使用されます。 nsmallest(k, iterable, key = fun) : この関数は、指定された反復可能オブジェクトから k 個の最小要素を返し、指定されている場合はキーを満たすために使用されます。
Python3
# Python code to demonstrate working of> # nlargest() and nsmallest()> # importing 'heapq' to implement heap queue> import> heapq> # initializing list> li1>=> [>6>,>7>,>9>,>4>,>3>,>5>,>8>,>10>,>1>]> # using heapify() to convert list into heap> heapq.heapify(li1)> # using nlargest to print 3 largest numbers> # prints 10, 9 and 8> print>(>'The 3 largest numbers in list are : '>, end>=>'')> print>(heapq.nlargest(>3>, li1))> # using nsmallest to print 3 smallest numbers> # prints 1, 3 and 4> print>(>'The 3 smallest numbers in list are : '>, end>=>'')> print>(heapq.nsmallest(>3>, li1))> |
>
>出力
The 3 largest numbers in list are : [10, 9, 8] The 3 smallest numbers in list are : [1, 3, 4]>
例：
Python3
マックOSとは何ですか
import> heapq> # Initialize a list with some values> values>=> [>5>,>1>,>3>,>7>,>4>,>2>]> # Convert the list into a heap> heapq.heapify(values)> # Print the heap> print>(>'Heap:'>, values)> # Add a new value to the heap> heapq.heappush(values,>6>)> # Print the updated heap> print>(>'Heap after push:'>, values)> # Remove and return the smallest element from the heap> smallest>=> heapq.heappop(values)> # Print the smallest element and the updated heap> print>(>'Smallest element:'>, smallest)> print>(>'Heap after pop:'>, values)> # Get the n smallest elements from the heap> n_smallest>=> heapq.nsmallest(>3>, values)> # Print the n smallest elements> print>(>'Smallest 3 elements:'>, n_smallest)> # Get the n largest elements from the heap> n_largest>=> heapq.nlargest(>2>, values)> # Print the n largest elements> print>(>'Largest 2 elements:'>, n_largest)> |
>
>出力
Heap: [1, 4, 2, 7, 5, 3] Heap after push: [1, 4, 2, 7, 5, 3, 6] Smallest element: 1 Heap after pop: [2, 4, 3, 7, 5, 6] Smallest 3 elements: [2, 3, 4] Largest 2 elements: [7, 6]>
このプログラムは、Python の heapq モジュールを使用してヒープ キューを作成し、リストのヒープへの変換、ヒープへの新しい値の追加、ヒープからの最小の要素の削除、ヒープから n 個の最小要素と最大 n 個の要素の取得などのさまざまな操作を実行します。山。
注記 Python の heapq モジュールは、ヒープ用に別のデータ構造を作成せずに、リストに対してヒープ操作をインプレースで実行する関数を提供します。 heapq モジュールは効率的で使いやすいため、Python で優先キューやその他のデータ構造を実装するための一般的な選択肢となっています。
Python でヒープ キュー (または heapq) を使用する利点:
- 効率的 : ヒープ キューは、Python で優先キューとヒープを管理するための非常に効率的なデータ構造です。これは、多くの操作に対して対数的な時間計算量を提供するため、多くのアプリケーションで一般的な選択肢となっています。スペース効率の高い : ヒープ キューは要素を配列ベースの表現で格納するため、スペース効率が高く、リンク リストなどのノードベースのデータ構造に関連するオーバーヘッドを最小限に抑えます。使いやすさ : Python のヒープ キューは使いやすく、シンプルで直感的な API を備えているため、ヒープへの要素の挿入、削除、取得などの基本的な操作を簡単に実行できます。柔軟性 : Python のヒープ キューを使用すると、優先キュー、ヒープ、バイナリ ツリーなどのさまざまなデータ構造を実装できるため、多くのアプリケーションにとって汎用性の高いツールになります。
Python でヒープ キュー (または heapq) を使用する場合の欠点:
- 機能の制限 : ヒープ キューは主に優先キューとヒープを管理するために設計されており、より複雑なデータ構造やアルゴリズムには適さない場合があります。ランダム アクセスなし: ヒープ キューは要素へのランダム アクセスをサポートしていないため、ヒープの中央にある要素にアクセスしたり、ヒープの先頭にない要素を変更したりすることが困難になります。並べ替えなし: ヒープ キューは並べ替えをサポートしていないため、要素を特定の順序で並べ替える必要がある場合は、別のデータ構造またはアルゴリズムを使用する必要があります。スレッドセーフではない : ヒープ キューはスレッドセーフではありません。つまり、データ同期が重要なマルチスレッド アプリケーションでの使用には適さない可能性があります。
全体として、ヒープ キューは、Python で優先キューとヒープを管理するための非常に効率的で柔軟なデータ構造ですが、機能が制限されている可能性があり、すべてのアプリケーションに適しているわけではありません。