ヒープソートのGolang実装

ヒープ ソートは、バイナリ ヒープ データ構造に基づく一般的な並べ替えアルゴリズムです。その時間計算量は O(nlogn) であり、大規模なデータの並べ替え問題の処理に使用できます。この記事では、golang でのヒープソートの実装を紹介します。

1. ヒープ ソートの概要

ヒープは完全なバイナリ ツリーであり、各ノードは親ノードの値以上 (または以下) を満たします。 to) その子ノードの値。これは、大きいルート パイル (または小さいルート パイル) と呼ばれます。ヒープ ソートでは、ヒープの特性を利用してソート対象の要素をヒープに編成し、ヒープが空になるまでヒープの先頭要素を 1 つずつ削除して順序付けされた結果を取得します。

次は、ヒープ ソートの簡単なプロセスです。

1. 大きなルート ヒープを例として、ソートする要素の初期ヒープを構築します。現在のノードの値がその子より小さい (または大きいか等しい) ノードの値が変更されると、2 つのノードの位置が交換されるため、処理後はルート ノードが最大 (または最小) になります。 ） 要素。
2. ルート ノードを最後の要素と交換し、最大の要素が最後に配置されます。
3. 残りの要素からヒープを再構築し、ルート ノードを取り出して残りの要素の最後に配置します。
4. ヒープが空になり並べ替えが完了するまで、2 と 3 を繰り返します。

2. コードの実装

ヒープ ソートの実装には、大規模なルート ヒープのアイデアを使用する必要があり、スライスを使用してヒープを保存できます。以下は、ヒープ ソートの Golang 実装です。

func heapSort(arr []int) {
    length := len(arr)
    // 构建初始堆
    for i := (length - 2) / 2; i >= 0; i-- {
        heapify(arr, i, length)
    }
    // 逐个取出堆顶元素
    for i := length - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, 0, i)
    }
}

func heapify(arr []int, index, length int) {
    left := 2*index + 1
    right := 2*index + 2
    maxIndex := index

    if left < length && arr[left] > arr[maxIndex] {
        maxIndex = left
    }

    if right < length && arr[right] > arr[maxIndex] {
        maxIndex = right
    }

    if maxIndex != index {
        arr[index], arr[maxIndex] = arr[maxIndex], arr[index]
        heapify(arr, maxIndex, length)
    }
}

このコードでは、 heapify 関数がヒープの構築と調整を実装します。ヒープの最後の非リーフ ノード (つまり、最後のノードの親ノード) から開始して、ルート ノードまで進みます。各ノードについて、左右の子ノードとのサイズ関係を判断する必要があり、左右の子ノードのいずれかが親ノードより大きい場合は、そのノードを親ノードと交換します。これを一度処理すると、ルートノードが最大値になります。ヒープソートでは、毎回ルートノードを取り出してヒープが空になるべき位置に配置し、残りの要素に対して再度ヒープを構築します。

main 関数では、heapSort 関数を呼び出して配列の並べ替えを完了するだけです:

func main() {
    arr := []int{5, 6, 7, 8, 1, 2, 3, 4, 0}
    fmt.Println(arr)
    heapSort(arr)
    fmt.Println(arr)
}

出力結果:

[5 6 7 8 1 2 3 4 0]
[0 1 2 3 4 5 6 7 8]

3. 概要

ヒープ ソートは、時間計算量が O(nlogn) の効率的なソート アルゴリズムです。 golang では、スライスを通じてヒープ ストレージを実装し、heapify 関数を通じてヒープを構築および調整できます。他の並べ替えアルゴリズムと比較して、ヒープ ソートはメモリ消費量が少なく、大規模なデータを処理する際の計算速度が速くなります。同時に、ヒープ ソートも不安定であり、要素の相対的な順序を変更しない必要がある状況には適していません。

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