algorithm
Tri du tas

Informations de base sur le tri du tas

Le tri du tas est une technique de tri basée sur la comparaison sur la structure de données du tas binaire. Il est similaire au tri par sélection dans lequel nous trouvons d'abord l'élément maximum et le mettons à la fin de la structure de données. Répétez ensuite le même processus pour les éléments restants.

Pseudo-code pour le tri du tas:

function heapsort(input, count)
    heapify(a,count)
    end <- count - 1
    while end -> 0 do
    swap(a[end],a[0])
    end<-end-1
    restore(a, 0, end)

function heapify(a, count)
    start <- parent(count - 1)
    while start >= 0 do
        restore(a, start, count - 1)
        start <- start - 1

Exemple de tri de tas:

Espace auxiliaire: O(1)
Complexité temporelle: O(nlogn)

Implémentation C #

public class HeapSort
{
    public static void Heapify(int[] input, int n, int i)
    {
        int largest = i;
        int l = i + 1;
        int r = i + 2;

        if (l < n && input[l] > input[largest])
            largest = l;

        if (r < n && input[r] > input[largest])
            largest = r;

        if (largest != i)
        {
            var temp = input[i];
            input[i] = input[largest];
            input[largest] = temp;
            Heapify(input, n, largest);
        }
    }

    public static void SortHeap(int[] input, int n)
    {
        for (var i = n - 1; i >= 0; i--)
        {
            Heapify(input, n, i);
        }
        for (int j = n - 1; j >= 0; j--)
        {
            var temp = input[0];
            input[0] = input[j];
            input[j] = temp;
            Heapify(input, j, 0);
        }
    }

    public static int[] Main(int[] input)
    {
        SortHeap(input, input.Length);
        return input;
    }
}