min-heap を使用したヒープの降順ソート

ヒープ ソート - ヒープ ソートは、バイナリ ツリー データ構造を使用して数値のリストを昇順または降順に並べ替える、比較ベースのアルゴリズムです。ルートが最小の要素であるヒープ ソートによってヒープ データ構造を作成し、ルートを削除してルート位置にリスト内で 2 番目に小さい番号を与えて再度ソートします。

最小ヒープ - 最小ヒープは、親ノードが子ノードよりも常に小さいデータ構造であるため、ルート ノードはすべての要素の中で最小の要素になります。

＃＃＃問題文＃＃＃

整数の配列が与えられます。 min-heap を使用して降順に並べ替えます。

例 1

リーリー リーリー

例 2

リーリー リーリー

方法1

最小ヒープを使用して降順でヒープソートを実行するには、要素の最小ヒープを作成し、一度に 1 つの要素を抽出して、順序を逆にして降順の配列を取得します。

疑似コード

リーリー

例: C 実装

次のプログラムでは、min-heap を使用して配列を並べ替え、順序を逆にして結果を取得します。

リーリー ＃＃＃出力＃＃＃ リーリー

時間計算量

- O(nlogn)

空間複雑度 - O(n)

方法 2 この問題に対するもう 1 つの解決策は、最後の非リーフ ルート パターンから開始して逆方向に作業して最小ヒープを構築することです。次に、ルート ノードと最後のリーフ ノードを交換して配列を並べ替え、min-heap プロパティを復元します。

疑似コード

リーリー

例: C 実装

次のプログラムでは、heapify() 関数を使用してインデックス i をルートとするサブツリーの最小ヒープ プロパティを復元し、heapSort() を使用して逆の順序で最小ヒープを構築します。

リーリー ＃＃＃出力＃＃＃ リーリー

heapSort() 関数を使用して最小ヒープを作成する前述の方法を使用すると、このソリューションでも同じ方法を使用できますが、最小ヒープのプロパティを復元するために heapify を使用する代わりに、従来の hep を使用します。 amin を作成するソート アルゴリズム ヒープとソートされた要素の順序が増分され、さらに逆転されて、目的の出力が得られます。

疑似コード

リーリー

例: C 実装

次のプログラムでは、ヒープ ソート アルゴリズムを変更して、配列を降順にソートします。

リーリー ＃＃＃出力＃＃＃ リーリー ＃＃＃結論は＃＃＃

要約すると、最小ヒープを使用して降順ヒープ ソートを実行するには、さまざまな方法を使用できます。その一部の時間計算量は O(nlogn) であり、各方法の空間計算量は異なります。

以上がmin-heap を使用したヒープの降順ソートの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。