ヒープソートに関する質問があります。それはアルゴリズムの本で述べているA.heap-size<= A.length 私は2つの違いを理解していない。配列がヒープを表す場合、A.heap-sizeがA.lengthより小さい可能性があります。私はA.heap-sizeがヒープ内の要素の数を表していることを知っています、なぜそれは完全に配列内の項目の数に等しいだけではありませんか？A.lengthとA.heap-sizeの違いは何ですか？
ヒープソートの不変量は、n要素配列の最初のk要素がk最小要素のヒープであり、最後のn-k要素がソート順のn-k最大要素であることです。後者の要素は、ヒープが配列全体を占有しない理由です。
あなたはもっと具体的になりますか？私は違いを理解できませんでした – caesar
ちょうど答えを広げる。その本をさらに読む。
A.heap_sizeの配列は、ヒープ（max_heapまたはmin_heap）構造要素が配置される場所です。並べ替えやキューイングの範囲で意味があります。あなたは正しい：これはヒープ内の要素の数ですが、それはヒープソートの最初の繰り返しでA.lengthに等しいです。次の反復で
、A[i] = A[A.length]（アレイA内の最後の要素）とmax_heapツリー（A[1]）のルートを交換した後に、A[1]要素がAの最後の要素となり、A.heap_sort値は1とmax_heap減少します構造体はmax_heapified：A[Parent(i)] >= A[i]でなければなりません。Parent(i)はヒープツリーのi/2を返します。
： を 
A.lengthはありません与えられたA.heapサイズのに対し、配列の要素の合計与えます（これは私を助けた）にあるどの要素のノーヒーププロパティ........およびA.length-A.heapサイズに従っている要素のソートされた順序またはいいえ、または今でもソートされていないし、将来ソートする必要があります。
書籍のヒープソートの実装のように、ヒープの配列の最初のセクションとソートされた要素の配列の2番目のセクションを使用します。ヒープは 'A.length'要素で始まりますが、max要素を削除するとヒープが縮小します。 – rliu