`container/heap.Init` în Go

Funcțiile de bază ale unui heap (coadă de priorități): Init îl organizează, Push adaugă, Pop scoate elementul cel mai mic.

Sintaxă

import "container/heap"

type Interface interface {
    sort.Interface   // Len, Less, Swap
    Push(x any)
    Pop() any
}

func Init(h Interface)
func Push(h Interface, x any)
func Pop(h Interface) any

Ce face `container/heap.Init`

Un heap este o structură care îți dă mereu rapid elementul „cel mai mic” (după Less), chiar dacă adaugi și scoți elemente des. Este baza unei cozi de priorități: pacienți după urgență, sarcini după termen, drumuri după distanță (algoritmul lui Dijkstra).

Pachetul container/heap nu are un tip gata făcut. Tu definești un tip (de obicei un slice) cu metodele Len, Less, Swap, Push și Pop, iar pachetul se ocupă de ordine. heap.Init(h) organizează datele existente, heap.Push(h, x) adaugă un element, iar heap.Pop(h) scoate și returnează elementul minim. Ambele durează O(log n).

Atenție: metodele Push/Pop ale tipului tău doar adaugă și scot la finalul slice-ului. Le apelează pachetul. Tu apelezi întotdeauna funcțiile heap.Push(h, x) și heap.Pop(h), nu metodele h.Push/h.Pop. Pentru maxim în loc de minim, inversează comparația din Less.

Parametri

Parametru	Descriere
`h`	Heap-ul: un pointer la tipul tău care implementează `heap.Interface`.
`x`	Pentru `Push`: elementul adăugat.

Ce returnează

Init și Push: nimic. Pop: elementul minim, ca any (faci conversia cu .(int) etc.).

Exemple

Exemplul 1: Heap de întregi: scoaterea în ordine crescătoare

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 any)        { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() any {
    vechi := *h
    n := len(vechi)
    x := vechi[n-1]
    *h = vechi[:n-1]
    return x
}

func main() {
    h := &MinHeap{8, 3, 10, 1}
    heap.Init(h)
    heap.Push(h, 5)
    fmt.Println("Minimul:", (*h)[0])
    for h.Len() > 0 {
        fmt.Print(heap.Pop(h), " ")
    }
    fmt.Println()
}

Rezultat

Minimul: 1
1 3 5 8 10

Exemplul 2: Coada de la urgențe

Less folosește >, deci iese întâi pacientul cu urgența cea mai mare.

package main

import (
    "container/heap"
    "fmt"
)

type Pacient struct {
    Nume    string
    Urgenta int
    index   int
}

type Coada []*Pacient

func (c Coada) Len() int           { return len(c) }
func (c Coada) Less(i, j int) bool { return c[i].Urgenta > c[j].Urgenta }
func (c Coada) Swap(i, j int) {
    c[i], c[j] = c[j], c[i]
    c[i].index = i
    c[j].index = j
}
func (c *Coada) Push(x any) {
    p := x.(*Pacient)
    p.index = len(*c)
    *c = append(*c, p)
}
func (c *Coada) Pop() any {
    vechi := *c
    n := len(vechi)
    p := vechi[n-1]
    vechi[n-1] = nil
    p.index = -1
    *c = vechi[:n-1]
    return p
}

func main() {
    c := &Coada{}
    heap.Init(c)
    heap.Push(c, &Pacient{Nume: "Ana", Urgenta: 2})
    heap.Push(c, &Pacient{Nume: "Mihai", Urgenta: 5})
    heap.Push(c, &Pacient{Nume: "Ioana", Urgenta: 3})
    heap.Push(c, &Pacient{Nume: "Radu", Urgenta: 1})
    for c.Len() > 0 {
        p := heap.Pop(c).(*Pacient)
        fmt.Printf("%s (urgență %d)\n", p.Nume, p.Urgenta)
    }
}