Pythonヒープキューアルゴリズム

ヒープデータ構造を使用して、優先キューを表すことができます。 Pythonでは、heapqモジュールで利用できます。ここでは、最小ヒープが作成されます。したがって、優先度が1の場合、それは最高の優先度を表します。新しい要素が挿入されると、ヒープ構造が更新されます。

このモジュールを使用するには、-

import heapq

ヒープ関連の操作がいくつかあります。これらは-

メソッドheapq.heapify（iterable）

反復可能なデータセットをヒープデータ構造に変換するために使用されます。

メソッドheapq.heappush（heap、element）

このメソッドは、要素をヒープに挿入するために使用されます。その後、ヒープ構造全体を再ヒープします。

メソッドheapq.heappop（heap）

このメソッドは、ヒープの先頭から要素を返したり削除したり、残りの要素に対してヒープ化を実行したりするために使用されます。

メソッドheapq.heappushpop（heap、element）

このメソッドは、1つのステートメントに要素を挿入してポップするために使用されます。

メソッドheapq.heapreplace（heap、element）

このメソッドは、1つのステートメントに要素を挿入してポップするために使用されます。ヒープのルートから要素を削除してから、要素をヒープに挿入します。

メソッドheapq.nlargest（n、iterable、key =None）

このメソッドは、ヒープから最大のn個の要素を返すために使用されます。

メソッドheapq.nsmallest（n、iterable、key =None）

このメソッドは、ヒープからn個の最小要素を返すために使用されます。

サンプルコード

import heapq
my_list = [58, 41, 12, 17, 89, 65, 23, 20, 10, 16, 17, 19]
heapq.heapify(my_list)
print(my_list)
heapq.heappush(my_list, 7)
print(my_list)
print('Popped Element: ' + str(heapq.heappop(my_list)))
print(my_list)
new_iter = list()
new_iter = heapq.nlargest(4, my_list)
print(new_iter)

出力

[10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65]
[7, 16, 10, 17, 17, 12, 23, 20, 41, 89, 58, 65, 19]
Popped Element: 7
[10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65]
[89, 65, 58, 41]