2

ヒープソートを使用してこれを降順にソートし、手順または説明を示してください。以下はツリーです

                             79
                       33           57
                    8     25    48

以下は配列です 79 - 33 - 57 - 8 - 25 - 48 ok 昇順は簡単です。最大の要素が一番上にあるため、最後の要素と最初の要素を交換してから、ウィキペディアのサンプル コードで説明されているように heapify を使用できます。

はっきりさせておきますが、ヒープは私が描いたツリー上に構築されています。昇順の手順はわかっていますが、配列は 8 - 25 - 33 - 48 - 57 - 79 のようになります。しかし、降順の手順は何ですか。これは非常に率直な質問です。配列を降順に並べ替えるために必要な手順を説明するだけです。

4

1 に答える 1

2

これは max heapのように見えるので、降順でソートするのは簡単です:

FUNCTION descSortedFrom(Heap h) : Array

   LET N := h.size
   LET ret := NEW Array (size = N)

   FOR i = 0..N-1 DO
      ret[i] := h.deleteMax

   RETURN ret

バイナリ ヒープ、二項ヒープ、およびフィボナッチ ヒープはすべて、最大ヒープでの deleteMax (または同様に、最小ヒープでの deleteMin) をサポートしてO(log N)いるため、全体としてこれはO(N log N)であり、比較ベースの並べ替えに最適です。

これは、簡単にするために外部ストレージ アレイを使用することに注意してください。ヒープと同じ配列を使用することを主張する場合は、単純に昇順で並べ替えてから、(何だと思いますか?) で配列を逆にしO(N)ます。

代替ソリューション

これは必要以上に複雑ですが、ワンパスでインプレースです。基本的に、配列要素[0..k)をヒープ要素として扱う代わりに、代わりに取得[N-k..N)します。heapifyこの変更に対応するには、開始オフセットを取得するように変更する必要があります。

お分かりのように、昇順で並べ替える方法は次のとおりです。

entire array = [ the heap elements ; the sorted asc elements ]

基本的に、並べ替えられた asc 要素を右から左に構築し、ヒープの最初 (最大値) をヒープの最後の要素と交換し、ヒープ サイズを 1 つ縮小してから、残りのヒープ要素をヒープ化します。

降順でソートすることは、概念的には同じです。

entire array = [ the sorted desc elements ; the heap elements ]

ソートされた desc 要素を左から右に作成します。ヒープの最大値を再配置する必要はありません。単純にヒープ サイズを 1 つ縮小しますが、末尾ではなく先頭で切り捨てます。heapifyしたがって、配列内でヒープ要素が実際に始まる場所を認識できるように、offset 引数を指定する必要があります。

于 2010-06-01T04:45:38.353 に答える