。 ここで、この事実の証拠を示します。
これは、Pascalの配列上にヒープを構築する手順の例です。
procedure siftdown(v:longint); var min,l,r:longint; begin l:=v*2; r:=v*2+1; min:=v; if (l <= s) and (a[l] < a[min]) then min:=l; if (r <= s) and (a[r] < a[min]) then min:=r; if min <> v then begin swap(a[min], a[v]); sift_down(min); end; end; procedure build; var i:longint; begin for i:=n downto 1 do siftdown(i); end;
だから、で構成される配列を与えましょう
要素、および 
オペレーター呼び出しの数 
（手順で 
）この配列でヒープを構築するとき。 明らかに 手順の操作時間を決定します 
これは私たちにとって興味深いです。
補題。
呼び出されたときに配列のいくつかの要素をみましょう 終わった 
オペレーターコール 。 その後、そのインデックスは超えませんでした 
。
証明：
で
オペレーターコール インデックス 
少なくとも要素が増加する 
回。 さあ 
、つまり 
。 その後 電話があります 
それは不可能です 要素。 
数量を推定しましょう
。 配列要素にインデックスを持たせる 。 見つけるだろう そのような 
。 次に、インデックス付きの要素を配列するために ヒープ上の所定の位置に落ちたので、これ以上は不要 呼び出します （補題による）。 そのようなインデックスを持つ要素の数は値です 
どの 
消えます。
このように
で
項はゼロです（したがって、手順のサイクル で始めることができます 
）
合計の各項の左因子を次のように推定します
ここから：
それぞれの合計を評価します。
このように
。
上にある関数によって制限される 。 手段 
。
したがって、手順の操作時間
比例する値があります 。