`container/heap.Fix` în Go

Fix reorganizează heap-ul după ce elementul de la indicele i s-a schimbat; Remove scoate elementul de la indicele i.

Sintaxă

import "container/heap"

func Fix(h Interface, i int)      // Go 1.2
func Remove(h Interface, i int) any

Ce face `container/heap.Fix`

Într-o coadă de priorități, prioritatea unui element se poate schimba (un pacient se simte mai rău). După ce modifici elementul de la indicele i, apelezi heap.Fix(h, i) și heap-ul își reface ordinea în O(log n). Este mai rapid decât Remove urmat de Push.

heap.Remove(h, i) scoate și returnează elementul de la indicele i, nu neapărat minimul (un pacient pleacă din coadă).

Pentru amândouă trebuie să știi indicele curent al elementului în slice, care se schimbă la fiecare operație. De aceea elementele țin un câmp index, actualizat în Swap, Push și Pop.

Parametri

Parametru	Descriere
`h`	Heap-ul.
`i`	Indicele elementului modificat sau scos.

Ce returnează

Fix: nimic. Remove: elementul scos, ca any.

Exemple

Exemplul 1: Schimbarea urgenței și plecarea unui pacient

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() {
    ana := &Pacient{Nume: "Ana", Urgenta: 2}
    radu := &Pacient{Nume: "Radu", Urgenta: 1}
    c := &Coada{}
    for _, p := range []*Pacient{ana, {Nume: "Mihai", Urgenta: 5}, {Nume: "Ioana", Urgenta: 3}, radu} {
        heap.Push(c, p)
    }

    ana.Urgenta = 9 // Ana se simte mai rău
    heap.Fix(c, ana.index)

    plecat := heap.Remove(c, radu.index).(*Pacient)
    fmt.Println("A plecat:", plecat.Nume)

    for c.Len() > 0 {
        p := heap.Pop(c).(*Pacient)
        fmt.Printf("%s (urgență %d)\n", p.Nume, p.Urgenta)
    }
}

Rezultat

A plecat: Radu
Ana (urgență 9)
Mihai (urgență 5)
Ioana (urgență 3)

Exemplul 2: Fix și Remove pe un heap de întregi

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{4, 7, 9, 12}
    heap.Init(h)
    (*h)[0] = 15 // minimul devine cel mai mare
    heap.Fix(h, 0)
    fmt.Println("Noul minim:", (*h)[0])

    scos := heap.Remove(h, 1)
    fmt.Println("Scos:", scos)
    for h.Len() > 0 {
        fmt.Print(heap.Pop(h), " ")
    }
    fmt.Println()
}