O（n）時間の複雑さで最小最大ヒープを構築する

Question

ウィキペディアによると、これは最小ヒープ：https://en.wikipedia.org/wiki/Min-max_heapです。私はO（n）にこのmin-maxヒープを構築する方法があるかどうか疑問に思っていました。私はminヒープとmaxヒープの両方でこれを行うことができると知っていますが、これに対するアプローチは何か分かりません。要素を挿入するとO（log n）時間の複雑さがかかり、この種のツリーはO（n log n）より効率的に構築できないような気がしますが、誰かが答えを持っていることを願っています。ありがとう。

Answer 1

はい、可能です。 ビルド・ヒープループでは、最小ヒープまたは最大ヒープと同様に、単に​​を呼び出します。その関数は、それが最小レベルか最大レベルかに応じて、それに応じてアイテムを移動します。

一般的な情報については、オリジナルペーパーMin-Max Heaps and Generalized Priority Queuesを参照してください。このペーパーでは、ビルドヒープは実装されていませんが、​​を呼び出す独自のコードを記述すると、期待通りに機能します。すなわち：

for i = A.length/2 downto 0 
    TrickleDown(i) 

​​はiが分レベルまたは最大レベルにあるかどうかを判断し、適切な方法、TrickleDownMin又はTrickleDownMaxを呼び出します。