Pelaksanaan golang sorting timbunan

Isih Timbunan ialah algoritma isihan biasa berdasarkan struktur data timbunan binari. Kerumitan masanya ialah O(nlogn) dan boleh digunakan untuk menangani masalah pengisihan data berskala besar. Artikel ini akan memperkenalkan pelaksanaan pengisihan timbunan dalam golang.

1. Pengenalan kepada pengisihan timbunan

Timbunan ialah pokok binari yang lengkap, di mana setiap nod memenuhi syarat bahawa nilai nod induk lebih besar daripada atau sama dengan (atau kurang daripada atau sama dengan) nilai nod anaknya, yang dipanggil Longgokan akar besar (atau longgokan akar kecil). Isihan timbunan menggunakan ciri timbunan untuk menyusun unsur untuk diisih ke dalam timbunan, dan kemudian mengalih keluar elemen atas timbunan satu demi satu sehingga timbunan kosong untuk mendapatkan hasil yang tersusun.

Berikut ialah proses mudah pengisihan timbunan:

1. Bina timbunan awal untuk unsur-unsur yang akan diisih, mengambil timbunan akar yang besar sebagai contoh, iaitu, jika nilai nod semasa adalah kurang daripada (atau lebih besar daripada atau sama dengan) anaknya Jika nilai nod diubah, kedudukan kedua-dua nod ditukar, supaya selepas pemprosesan, nod akar adalah yang terbesar (atau terkecil ) unsur.
2. Tukar nod akar dengan elemen terakhir, dan elemen terbesar diletakkan di hujung.
3. Bina semula timbunan daripada elemen yang tinggal, kemudian keluarkan nod akar dan letakkannya di hujung elemen yang tinggal.
4. Ulang 2 dan 3 sehingga longgokan itu dikeringkan dan pengasingan selesai.

2. Pelaksanaan kod

Pelaksanaan pengisihan timbunan memerlukan penggunaan idea timbunan akar yang besar Kita boleh menggunakan kepingan untuk menyimpan timbunan. Berikut ialah pelaksanaan golang pengisihan timbunan:

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)
    }
}

Dalam kod ini, fungsi heapify melaksanakan pembinaan dan pelarasan timbunan. Kami bermula dari nod bukan daun terakhir timbunan (iaitu, nod induk nod terakhir) dan bekerja ke atas sehingga nod akar. Untuk setiap nod, kita perlu menentukan hubungan saiznya dengan nod anak kiri dan kanan Jika salah satu nod anak kiri dan kanan lebih besar daripada nod induk, maka tukar nod dengan nod induk. Selepas memproses ini sekali, nod akar adalah nilai maksimum. Dalam pengisihan timbunan, kami mengeluarkan nod akar setiap kali dan meletakkannya dalam kedudukan di mana timbunan harus kosong, dan kemudian membina timbunan semula untuk elemen yang tinggal.

Dalam fungsi utama, anda hanya perlu memanggil fungsi heapSort untuk melengkapkan pengisihan tatasusunan:

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

Hasil output:

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

3. Ringkasan

Isihan timbunan ialah algoritma isihan yang cekap dengan kerumitan masa O(nlogn). Dalam golang, kita boleh melaksanakan penyimpanan timbunan melalui penghirisan, dan kemudian membina dan melaraskan timbunan melalui fungsi heapify. Berbanding dengan algoritma pengisihan lain, isihan timbunan menggunakan lebih sedikit memori dan mempunyai kelajuan pengiraan yang lebih pantas apabila memproses data berskala besar. Pada masa yang sama, pengisihan timbunan juga tidak stabil dan tidak sesuai untuk situasi di mana susunan relatif elemen diperlukan untuk kekal tidak berubah.

Atas ialah kandungan terperinci Pelaksanaan golang sorting timbunan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!