O（k）時間のn = 2^k個の要素で2つのヒープをマージするアルゴリズムを実装する方法は？

Question

しかし、私はこの問題の意味を知りません。

これは2つのソートされた配列をマージするためにO（n）の最小時間しかかかりませんが、O（k）時間でマージする方法はわかりません。

この問題の目的は、トップダウン方式で効率的に標準のヒープを構築する可能性を探ることである。

これは、それに関連する3つの問題の合計です。

1. それぞれが正確にn = 2^k個の要素を含む2つの標準ヒープをマージするアルゴリズムの概要を示します。このアルゴリズムは、O（k）時間で実行されるべきである。

2. パート1で指定されたサブルーチンを使用して、2^n要素のヒープを構築する再帰的または反復的なアルゴリズムを与えます。

3. パート2で指定したアルゴリズムの実行時間の式を書き留めてください。

Answer 1

あなたがBinomial_heapまたは Leftist heaps使用することができます。

n = 2^kの場合、それらはすべてO（k）時間でマージ操作を行います。