Comment implémenter min-heap en langage Go

Min-heap est une structure de données qui permet de trouver rapidement le plus petit élément. En langage Go, nous pouvons utiliser le package heap pour implémenter le tas minimum. Dans cet article, nous détaillerons comment implémenter min-heap en langage Go.

Qu'est-ce qu'un min-heap ?

Min tas est une structure arborescente binaire qui satisfait les deux conditions suivantes :

1. La valeur du nœud parent est inférieure ou égale à la valeur de son nœud enfant.
2. Chaque niveau est rempli de gauche à droite.

Par exemple, ce qui suit est un tas min :

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

Dans un tas min, le nœud racine est toujours le plus petit élément, donc la complexité temporelle pour trouver la valeur minimale est O(1). La complexité temporelle des opérations d'insertion et de suppression du tas minimum est O(log n).

Comment implémenter le min-heap ?

En langage Go, nous pouvons utiliser le package heap pour implémenter le tas minimum. Le package tas fournit les trois méthodes suivantes pour implémenter le tas minimum :

1. Init : Initialiser un tas minimum vide.
2. Push : insérez des éléments dans le min-heap.
3. Pop : supprime et renvoie le plus petit élément du min-heap.

Tout d'abord, nous devons définir une structure de données pour stocker les éléments. Dans cet article, nous utiliserons le type int comme éléments. Puisque nous devons convertir le type int en type heap.Interface, nous devons implémenter trois méthodes de l'interface heap.Interface : Len, Less et 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] }

Dans le code ci-dessus, nous avons défini un type MinHeap et implémenté les méthodes Len, Less et Swap. La méthode Len renvoie le nombre d'éléments dans le tas minimum, la méthode Less compare les tailles de deux éléments et la méthode Swap échange les positions de deux éléments.

Ensuite, nous devons implémenter la méthode d'initialisation minimale du tas. Nous pouvons utiliser la fonction heap.Init pour initialiser un min-heap vide.

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

Maintenant, nous avons initialisé un min-heap vide. Ensuite, nous pouvons utiliser la fonction heap.Push pour insérer des éléments.

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)

Dans le code ci-dessus, nous utilisons la fonction heap.Push pour insérer des éléments dans le min-heap.

Nous pouvons également utiliser la fonction heap.Pop pour supprimer et renvoyer le plus petit élément.

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

Dans le code ci-dessus, nous utilisons les fonctions loop et heap.Pop pour afficher tous les éléments du min-heap.

Code complet :

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

Dans le code ci-dessus, en plus d'implémenter les méthodes Len, Less et Swap, nous implémentons également les méthodes Push et Pop. La méthode Push insère un élément dans le tas min et la méthode Pop supprime l'élément du tas min et renvoie le plus petit élément.

Résumé

Cet article présente comment implémenter le tas minimum en langage Go. En utilisant les fonctions fournies par le package heap, nous pouvons rapidement implémenter un min-heap avec une complexité temporelle O(log n) lors de l'insertion et de la suppression d'éléments. Si vous devez implémenter d'autres types de tas, veuillez consulter la documentation du package tas.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!