Pythonのheapqモジュールを使って2つのソート済みリストをマージする方法

この記事では、Pythonのheapqモジュールを使用して、2つのソート済みリストを1つにマージする方法を解説します。

例えば、list1 = [10, 20, 30, 40]とlist2 = [100, 200, 300, 400, 500]という2つのリストがある場合、マージ後は[10, 20, 30, 40, 100, 200, 300, 400, 500]のような結果が得られます。

heapqモジュールとは

heapqはPythonに標準で搭載されているライブラリモジュールのため、追加のインストールは不要です。利用する前にインポートするだけで使えます。

import heapq

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個の要素を返します。

マージの実装例

それでは、実際にheapq.merge()を使って2つのソート済みリストをマージしてみましょう。

import heapq
first_list = [45, 12, 63, 95, 74, 21, 20, 15, 36]
second_list = [42, 13, 69, 54, 15]

first_list = sorted(first_list)
second_list = sorted(second_list)

print('First sorted list: ' + str(first_list))
print('Second sorted list: ' + str(second_list))

final_list = list(heapq.merge(first_list, second_list))
print('The final list: ' + str(final_list))

実行結果

First sorted list: [12, 15, 20, 21, 36, 45, 63, 74, 95]
Second sorted list: [13, 15, 42, 54, 69]
The final list: [12, 13, 15, 15, 20, 21, 36, 42, 45, 54, 63, 69, 74, 95]

まとめ

heapq.merge()を使えば、ソート済みの複数のリストを効率的に1つのソート済みリストへと統合できます。この関数はイテレータを返すため、大きなデータセットでもメモリ効率よく処理できるのが特徴です。リストとして扱いたい場合は、上記の例のようにlist()で変換しましょう。