Implémentation de Golang pour le tri de tas

Heap Sort est un algorithme de tri courant basé sur la structure de données du tas binaire. Sa complexité temporelle est O(nlogn) et peut être utilisée pour gérer des problèmes de tri de données à grande échelle. Cet article présentera l'implémentation du tri de tas dans Golang.

1. Introduction au tri par tas

Un tas est un arbre binaire complet, dans lequel chaque nœud satisfait que la valeur du nœud parent est supérieure ou égale à (ou inférieur ou égal à) la valeur de son nœud enfant, appelé grand tas racine (ou petit tas racine). Le tri par tas utilise les caractéristiques du tas pour organiser les éléments à trier en un tas, puis supprime les éléments supérieurs du tas un par un jusqu'à ce que le tas soit vide pour obtenir un résultat ordonné.

Ce qui suit est un processus simple de tri de tas :

1. Construisez un tas initial pour les éléments triés, en prenant comme exemple le grand tas racine, c'est-à-dire , si la valeur du nœud courant est inférieure (ou supérieure ou égale) à la valeur de son nœud enfant, les positions des deux nœuds sont échangées, de sorte qu'après traitement, le nœud racine soit le plus grand (ou le plus petit) élément.
2. Échangez le nœud racine avec le dernier élément, et le plus grand élément est placé à la fin.
3. Reconstruisez le tas à partir des éléments restants, puis retirez le nœud racine et placez-le à la fin des éléments restants.
4. Répétez 2 et 3 jusqu'à ce que le tas soit vidé et que le tri soit terminé.

2. Implémentation du code

L'implémentation du tri par tas nécessite l'utilisation de l'idée d'un grand tas racine Nous pouvons utiliser des tranches pour stocker le. tas. Voici l'implémentation golang du tri du tas :

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

Dans ce code, la fonction heapify implémente la construction et l'ajustement du tas. Nous partons du dernier nœud non-feuille du tas (c'est-à-dire le nœud parent du dernier nœud) et progressons jusqu'au nœud racine. Pour chaque nœud, nous devons déterminer sa relation de taille avec les nœuds enfants gauche et droit. Si l'un des nœuds enfants gauche et droit est plus grand que le nœud parent, échangez le nœud avec le nœud parent. Après avoir traité cela une fois, le nœud racine a la valeur maximale. Dans le tri du tas, nous retirons le nœud racine à chaque fois et le plaçons dans une position où le tas doit être vide, puis reconstruisons le tas pour les éléments restants.

Dans la fonction principale, il vous suffit d'appeler la fonction heapSort pour terminer le tri du tableau :

func main() {
    arr := []int{5, 6, 7, 8, 1, 2, 3, 4, 0}
    fmt.Println(arr)
    heapSort(arr)
    fmt.Println(arr)
}

Résultat de sortie :

[5 6 7 8 1 2 3 4 0]
[0 1 2 3 4 5 6 7 8]

3. Résumé

Le tri par tas est un algorithme de tri efficace avec une complexité temporelle de O(nlogn). Dans Golang, nous pouvons implémenter le stockage par tas via le découpage, puis créer et ajuster le tas via la fonction heapify. Comparé à d'autres algorithmes de tri, le tri par tas consomme moins de mémoire et offre une vitesse de calcul plus rapide lors du traitement de données à grande échelle. Dans le même temps, le tri par tas est également instable et ne convient pas aux situations où l'ordre relatif des éléments doit rester inchangé.

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!