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 :
/**
* 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());
}
}