Montée dans le tas

Cette section explique comment ajouter un élément à un tas max, appeléremontée。

Supposons que nous ajoutions un nouvel élément 52 au tas max ci-dessous, en le plaçant à la dernière position du tableau. Comme 52 est supérieur à son nœud parent 16, la propriété du tas n'est pas satisfaite et un ajustement est nécessaire.

Tout d'abord, échangez les valeurs aux indices 5 et 11 dans le tableau, c'est-à-dire échangez 52 et 16.

À ce stade, 52 est toujours supérieur à la valeur 41 à l'indice parent 2, nous devons donc le remonter davantage.

Maintenant, comparons 52 avec 62. Comme 52 est déjà plus petit que son parent, il n'a pas besoin de remonter davantage, et la propriété du tas max est satisfaite. Nous appelons ce processus remontée pour un tas max.

Exemple de code Java

Téléchargement du paquet de code source :Télécharger

Code du fichier src/example/heap/HeapShiftUp.java :

package example.heap;

/**
* Ajouter un élément au tas
 */

public class HeapShiftUp<T extends Comparable> {

    protected T[] data;
    protected int count;
    protected int capacity;

    // Constructeur, construit un tas vide pouvant contenir capacity éléments
    public HeapShiftUp(int capacity){
        data = (T[])new Comparable[capacity+1];
        count = 0;
        this.capacity = capacity;
    }
    // Retourne le nombre d'éléments dans le tas
    public int size(){
        return count;
    }

    // Retourne un booléen indiquant si le tas est vide
    public boolean isEmpty(){
        return count == 0;
    }
    // Insérer un nouvel élément item dans le tas max
    public void insert(T item){
        assert count + 1 <= capacity;
        data⟦⟧count[count+1] = item;
        count ++;
        shiftUp(count);
    }
    // Échanger les deux éléments aux indices i et j dans le tas
    private void swap(int i, int j){
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    //********************
    //* Fonctions utilitaires de base du tas max
    //********************
    private void shiftUp(int k){

        while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
            swap(k, k/2);
            k /= 2;
        }
    }

    // Test HeapShiftUp
    public static void main(String[] args) {
        HeapShiftUp<Integer> heapShiftUp = new HeapShiftUp<Integer>(100);
        int N = 50; // Nombre d'éléments dans le tas
        int M = 100; // Plage de valeurs des éléments du tas [0, M)
        for( int i = 0 ; i < N ; i ++ )
            heapShiftUp.insert( new Integer((int)(Math.random() * M)) );
        System.out.println(heapShiftUp.size());

    }
}
autres extensions