ヒープソートとはどのようなソートですか?

ヒープソートは、順序付けされていないシーケンスから最大ヒープを生成し、ヒープの先頭要素の位置を最後の要素と交換し、残りの要素を生成して最大ヒープを形成する方法です。要素は次のとおりです。最大のヒープを生成するために順次交換されます。

ヒープソート

順序のないシーケンスを最大のヒープに生成し、その先頭の要素を結合します。最後の要素の位置が交換され、残りの要素が生成されて最大ヒープが生成されます。要素は順番に交換され、最大ヒープが生成されます。

時間計算量: O(NlogN) 空間計算量: O(1)

はじめに:

#ヒープソート（英: Heapsort）とは、ヒープのデータ構造を利用して設計されたソートアルゴリズムを指します。ヒープは、完全なバイナリ ツリーに近似し、ヒーピング特性を満たす構造です。つまり、子ノードのキー値またはインデックスは常に親ノードより小さい (または大きい) ものです。

ヒープ操作

ヒープ データ構造では、ヒープ内の最大値は常にルート ノードに位置します (ヒープが優先キューで使用されている場合、ヒープ内の最小値はルート ノードにあります)。はルート ノードにあります)。

次の操作がヒープ内で定義されています:

Max Heapify: 子ノードが常に親ノードよりも小さくなるようにヒープの最後の子ノードを調整します

最大ヒープの作成: ヒープ内のすべてのデータを並べ替えます。

HeapSort: 最初のデータのルート ノードを削除し、最大ヒープ調整の再帰操作を実行します

以上がヒープソートとはどのようなソートですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。