n 要素の最小ヒープまたは最大ヒープを作成する場合、ヒープの作成にかかる時間は O(nlogn) になります。すべての挿入には O(logn) 時間がかかるため、n 個の要素には O(nlogn) 時間がかかるためです。
しかし、多くの場所で、ヒープの作成は O(n) 時間、つまり線形時間に最適化できると書かれていますが、その方法は明確に説明されていません。
質問する
6791 次
1 に答える
4
最適な方法は、ノードを挿入するためのログイン時間を必要としません。
最適な方法は、(ツリーは配列で表すことができるため) shape プロパティを考慮して、要素をバイナリ ツリーに任意に配置することから始まります。次に、最下位レベルから開始して上に移動し、ヒープ プロパティが復元されるまで、削除アルゴリズムのように各サブツリーのルートを下にシフトします。より具体的には、ある高さ
h(下から測定) で始まるすべてのサブツリーが既に「ヒープ化」されている場合、その高さのツリーは 、または最小値の子h+1を構築するときに、最大値の子のパスに沿ってルートを下に送ることによってヒープ化できます。max-heapを構築するときmin-heap。このプロセスにはO(h)ノードごとのスワップ操作。この方法では、ヒープ化のほとんどが下位レベルで行われます。ヒープの高さは であるため、高さlognのノード数は ですh。したがって、すべてのサブツリーをヒープ化するコストは次のとおりです。h=0 ∑<sup>logn n/2 h+1 = O(n * h=0 ∑<sup>lognh/2 h ) より小さい
O(n * h=0 ∑<sup>∞</sup>h/2 h )
since h / 2h converges to 2 as it is an infinite seriesそれは等しい
O(n)
ソース: http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
于 2012-05-19T10:15:29.830 に答える