Cara melaksanakan min-heap dalam bahasa Go

Min-heap ialah struktur data yang boleh mencari elemen terkecil dengan cepat. Dalam bahasa Go, kita boleh menggunakan pakej heap untuk melaksanakan heap minimum. Dalam artikel ini, kami akan memperincikan cara melaksanakan min-timbunan dalam bahasa Go.

Apakah timbunan min?

Timbunan min ialah struktur pokok binari yang memenuhi dua syarat berikut:

1. Nilai nod induk adalah kurang daripada atau sama dengan nilai nod anaknya.
2. Setiap tahap diisi dari kiri ke kanan.

Sebagai contoh, berikut ialah timbunan min:

      2
    /   \
   5     3
  / \   / \
 7   6 8   4

Dalam timbunan min, nod akar sentiasa elemen terkecil, jadi kerumitan masa untuk mencari nilai minimum ialah O( 1). Kerumitan masa operasi pemasukan dan pemadaman timbunan minimum ialah O(log n).

Bagaimana untuk melaksanakan timbunan minimum?

Dalam bahasa Go, kita boleh menggunakan pakej timbunan untuk melaksanakan timbunan minimum. Pakej timbunan menyediakan tiga kaedah berikut untuk melaksanakan timbunan minimum:

1. Init: Mulakan timbunan minimum kosong.
2. Tekan: Masukkan elemen ke dalam timbunan min.
3. Pop: Alih keluar dan kembalikan elemen terkecil daripada timbunan min.

Pertama, kita perlu mentakrifkan struktur data untuk menyimpan elemen. Dalam artikel ini, kami akan menggunakan jenis int sebagai elemen. Memandangkan kita perlu menukar jenis int kepada heap.Interface type, kita perlu melaksanakan tiga kaedah heap.Interface antara muka: Len, Less dan Swap.

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

Dalam kod di atas, kami mentakrifkan jenis MinHeap dan melaksanakan kaedah Len, Less dan Swap. Kaedah Len mengembalikan bilangan elemen dalam timbunan minimum, kaedah Less membandingkan saiz dua elemen, dan kaedah Swap menukar kedudukan dua elemen.

Seterusnya, kita perlu melaksanakan kaedah permulaan timbunan minimum. Kita boleh menggunakan fungsi heap.Init untuk memulakan timbunan min kosong.

h := &MinHeap{}
heap.Init(h)

Kini, kami telah memulakan timbunan min kosong. Seterusnya, kita boleh menggunakan fungsi heap.Push untuk memasukkan elemen.

heap.Push(h, 2)
heap.Push(h, 5)
heap.Push(h, 3)
heap.Push(h, 7)
heap.Push(h, 6)
heap.Push(h, 8)
heap.Push(h, 4)

Dalam kod di atas, kami menggunakan fungsi heap.Push untuk memasukkan elemen ke dalam timbunan min.

Kita juga boleh menggunakan fungsi heap.Pop untuk mengalih keluar dan mengembalikan elemen terkecil.

for h.Len() > 0 {
     fmt.Printf("%d ", heap.Pop(h))
}

Dalam kod di atas, kami menggunakan fungsi gelung dan timbunan.Pop untuk mengeluarkan semua elemen dalam timbunan min.

Kod penuh:

package main

import (
    "container/heap"
    "fmt"
)

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func main() {
    h := &MinHeap{}
    heap.Init(h)

    heap.Push(h, 2)
    heap.Push(h, 5)
    heap.Push(h, 3)
    heap.Push(h, 7)
    heap.Push(h, 6)
    heap.Push(h, 8)
    heap.Push(h, 4)

    for h.Len() > 0 {
        fmt.Printf("%d ", heap.Pop(h))
    }
}

Dalam kod di atas, selain melaksanakan kaedah Len, Less dan Swap, kami juga melaksanakan kaedah Push dan Pop. Kaedah Push memasukkan elemen ke dalam timbunan min, dan kaedah Pop mengalih keluar dan mengembalikan elemen terkecil daripada timbunan min.

Ringkasan

Artikel ini memperkenalkan cara melaksanakan timbunan minimum dalam bahasa Go. Dengan menggunakan fungsi yang disediakan oleh pakej timbunan, kami boleh melaksanakan timbunan min dengan cepat dengan kerumitan masa O(log n) apabila memasukkan dan memadam elemen. Jika anda perlu melaksanakan jenis timbunan lain, sila rujuk dokumentasi pakej timbunan.

Atas ialah kandungan terperinci Cara melaksanakan min-heap dalam bahasa Go. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!