algorithm - 最小ヒープで k 個の最小要素を見つける

Question

サイズ n の最小ヒープがあるとします。元の最小ヒープを変更せずに最小の k 要素を見つけたい。ランタイムは theta(k^2) である必要があります。メモリ theta(k) を使用できます。

どうすればいいですか？

Answer 1

疑似コードの例を次に示します。

candidates.add((heap[heap.root],heap.root))
while len(result)<k:
  (min_value,i)=candidates.remove_min()
  result.append(min_value)
  l=heap.left_child(i)
  r=help.right_child(i)
  candidates.add((heap[l],l))
  candidates.add((heap[r],r))

ヒープにはインデックスがあると想定されており、 を使用して任意のインデックスで値を取得できますheap[index]。最小値を含むルートのインデックスは ですheap.root。candidates値とヒープ インデックスのペアを含む、最初は空の 2 次最小ヒープです。に最小値がresult順番に格納されます。

ループは k 回実行されます。candidates.remove_min()O(log(k)) であるとを除いて、すべての操作は一定時間candidates.add()であるため、合計時間は O(k*log(k)) です。