arrays - A.length と A.heap-size の違いは何ですか?

Question

ヒープソートについて質問です。アルゴリズムの本A.heap-size<= A.length には、2つの違いがわかりません。配列がヒープを表す場合、なぜA.heap-sizeより小さい可能性があるのでしょうかA.length。がヒープ内の要素の数を表していることは知っていA.heap-sizeますが、配列内の項目の数と完全に等しくないのはなぜですか?

Answer 1

答えを広げるだけです。その本をさらに読んでください。

A.heap_size配列の、ヒープ (max_heap または min_heap) 構造要素が配置される場所です。ソートまたはキューイングの範囲で理にかなっています。おっしゃる通り、これはヒープ内の要素数ですが、ヒープ ソートの最初の繰り返しA.lengthでのみ等しいです。

次の反復で、max_heap ツリー ( A[1])のルートをA[i] = A[A.length](配列 A 内の最後の要素) と交換した後、A[1]要素は A の最後の要素になり、A.heap_sort値は 1 減らされ、max_heap 構造は max_heapified:A[Parent(i)] >= A[i]になる必要がありParent(i)ます。ヒープ ツリーの i/2。

Answer 2

ヒープソートの外側のループを k 回繰り返した後、配列は n-k 個の最小要素 (A.heap-size = n-k) 上の n-k 個の要素の最大ヒープと、それに続く k 個の最大要素が並べ替えられた順序 ( A.長さ = n)。