【Python】ヒープを使ってk番目に小さい要素を平均O(n)時間で求める方法

数値のリスト nums と整数 k が与えられたとき、リストの中で0番目から数えて k 番目に小さい要素を求めることを考えます。ただし、この問題は平均して線形時間 O(n) で解く必要があります。

例えば、入力が nums = [6, 4, 9, 3, 1]、k = 2 の場合を考えてみましょう。リストを昇順にソートすると [1, 3, 4, 6, 9] となるため、2番目(0始まり)に小さい要素は 4 であり、これが出力となります。

解法のアプローチ

この問題は「サイズ k+1 の最大ヒープ(max-heap)」を維持することで効率的に解けます。考え方のポイントは次のとおりです。

• 最初の k+1 個の要素を最大ヒープにすべて挿入する
• 残りの要素を順に走査し、現在のヒープ内の最大値よりも小さい要素が見つかったら、ヒープの最大値を取り除いて代わりにその要素を挿入する
• 走査が終わった時点で、ヒープには全体で k+1 個の最小要素が残っており、その根(最大値)がまさに k 番目に小さい要素になる

アルゴリズムの手順

1. 空の最大ヒープ maxHeap を用意する
2. i を 0 から k までループし、nums[i] を maxHeap に挿入する
3. i を k+1 から len(nums) - 1 までループする
   　もし nums[i] がヒープ内の最大値より小さければ、ヒープの先頭(最大値)を削除し、nums[i] を挿入する
4. 最後に maxHeap の根の値を返す

実装例

理解を深めるために、以下の実装を見てみましょう。Python標準ライブラリの heapq は最小ヒープのみを提供しているため、要素を負の値にして格納することで最大ヒープとして振る舞わせています。

from heapq import heappop, heappush

def solve(nums, k):
    maxHeap = []
    # 最初の k+1 個の要素をヒープに追加(負の値で最大ヒープを再現)
    for i in range(k + 1):
        heappush(maxHeap, -nums[i])
    # 残りの要素を走査
    for i in range(k + 1, len(nums)):
        if nums[i] < -maxHeap[0]:
            heappop(maxHeap)
            heappush(maxHeap, -nums[i])
    return -maxHeap[0]

nums = [6, 4, 9, 3, 1]
k = 2
print(solve(nums, k))

入力

[6, 4, 9, 3, 1], 2

出力

4

仕組みと計算量

ヒープのサイズは常に k+1 に保たれるため、挿入・削除の各操作は O(log k) のコストで行えます。k が n に比べて十分小さい場合、全体の処理は事実上線形時間で完了します。また、この手法はリスト全体をソートする O(n log n) のアプローチよりも高速であるうえ、必要なメモリも O(k) に抑えられるという実用的な利点があります。