Rumah >pembangunan bahagian belakang >Golang >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:
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!