3

次のような宿題の質問があります。

問題 1: 与えられた配列 [ 22 | 25 | 71 | 24 | 18 | 5 | 27 | 32 | 104 | 8 | 23 | 66 ] 配列の最大ヒープを構築します。詳細をスキップせずにすべての手順を表示します。

これは、インターネットでの調査からの max-heap に関する私の理解です。

最大ヒープは、親ノードが常に子ノードよりも大きく、「子を追加するたびに左側に追加して、ツリーが増加するたびに高さになるように、バイナリ ツリーでより簡単に表すことができる配列です。完全なツリーです」

とにかくこれは私が構築したものです

宿題の質問 2 を読むまでは、それが正しい答えだと思っていました。

問題 2: 問題 1 と同じ配列を使用して、Heapsort を使用して配列を並べ替えます。詳細をスキップせずにすべての手順を表示します。

今、私は混乱しています。多分私は問題番号2を答えました...

4

1 に答える 1

6

ツリーを構築していますが、配列を調整していません。配列はヒープ構造を反映しています。最初の要素は配列の最大の要素であり、次の2つの要素はその要素の左右の子です。

ヒープを構築した後、配列の最後の要素と最初の要素を交換してから、同じ配列で作業しますが、要素0 ... array.size-2のみを使用するという考え方です。ヒープ条件が無効であり、 heapifyを呼び出して、小さい配列で正しいヒープ構造を取得します。これにより、最初の位置にある小さな配列の中で最大の要素が再び得られます。小さい方の配列の最初と最後の要素を入れ替えて、要素が2つ少ない配列にヒープを構築します。ただし、最後に2つの要素がソートされています（配列全体の最大の要素と次に大きい要素（最初の小さい配列の最大の要素））。要素が残っていない残りの配列ができるまで、これを行います。

ドイツ語版ウィキペディアのヒープソート図をご覧ください。最初に、ソートされていない配列が表示されます。小さい黒いボックスは、アレイ内の位置を示します。最初のツリーはヒープです。

 Unsorted array
 23 | 1 | 6 | 19 | 14 | 18 | 8 | 24 | 15

 Heapified Array
 24 | 23 | 18 | 19 | 14 | 8 | 6 | 1 | 15

 First iteration
 Swap First (Biggest Element in Array) with last Element (could be anything)
 15 | 23 | 18 | 19 | 14 | 8 | 6 | 1 | 24

 heap condition is invalid

 Build heap on array.size - 2
 23 | 19 | 18 | 15 | 14 | 8 | 6 | 1 || 24

 Swap first and last element in smaller heap
 1 | 19 | 18 | 15 | 14 | 8 | 6 | 23 || 24

 Build heap on array.size - 3
 19 | 15 | 18 | 1 | 14 | 8 | 6 || 23 | 24

 Swap first and last element on that smaller heap and build heap on array.size - 4
 until you cant shrink the heap anymore, you'll receive
 || 1 | 8 | 14 | 15 | 18 | 19 | 23 | 24

不変条件は、各反復の前後でツリーがヒープになることです。それが機能する理由です。常に最大の要素をヒープ化された配列の最後にスワップするためです。

于 2012-03-26T23:05:06.150 に答える