Descente dans le tas
Cette section présentera comment retirer un élément d'un tas max, opération appelée descente. Seul l'élément ayant la plus haute priorité peut être retiré, c'est-à-dire le nœud racine. Après avoir retiré le 62 d'origine, ce qui suit explique comment remplir ce tas max.
La première étape consiste à placer le dernier élément du tableau au niveau du nœud racine. À ce stade, cela ne satisfait pas à la définition d'un tas max.
Le processus d'ajustement consiste à déplacer ce nœud racine 16 vers le bas, étape par étape. Comme 16 est plus petit que ses deux nœuds enfants, on compare d'abord les nœuds enfants 52 et 30 pour voir lequel est le plus grand, puis on échange sa position avec celle du plus grand.
On continue à comparer les nœuds enfants 28 et 41 de 16. Comme 41 est plus grand, 16 et 41 échangent leurs positions.
On continue à comparer 16 avec son nœud enfant 15. Comme 16 est plus grand, aucun échange n'est nécessaire maintenant. Enfin, notre opération de descente est terminée, en conservant la propriété d'un tas max.
4. Exemple de code Java
Téléchargement du paquet source :Télécharger
Code du fichier src/example/heap/HeapShiftDown.java :
/**
* Extraire un élément du tas max
*/
public class HeapShiftDown<T extends Comparable> {
protected T[] data;
protected int count;
protected int capacity;
// Constructeur, construit un tas vide pouvant contenir capacity éléments
public HeapShiftDown(int capacity){
// Le +1 ici fait référence au nombre d'éléments pouvant être stockés à l'origine ; après suppression de la position 0, il ne peut contenir que capacity éléments
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);
}
// le sommet du tas max, c'est-à-dire la plus grande donnée stockée dans le tas
public T extractMax(){
assert count > 0;
T ret = data[1];
swap( 1 , count );
count --;
shiftDown(1);
return ret;
}
// Obtenir l'élément au sommet du tas max
public T getMax(){
assert( count > 0 );
return data[1];
}
// É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;
}
}
// opération shiftDown
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k; // Dans cette itération de boucle, data[k] et data[j] échangent leurs positions
if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
j ++;
// data[j] est le maximum de data[2*k] et data[2*k+1]
if( data[k].compareTo(data[j]) >= 0 ) break;
swap(k, j);
k = j;
}
System.out.println("shiftDown terminé");
}
// Tester HeapShiftDown
public static void main(String[] args) {
HeapShiftDown<Integer> heapShiftDown = new HeapShiftDown<Integer>(100);
// Nombre d'éléments dans le tas
int N = 100;
// Plage de valeurs des éléments du tas [0, M)
int M = 100;
for( int i = 0 ; i < N ; i ++ )
heapShiftDown.insert( new Integer((int)(Math.random() * M)) );
Integer[] arr = new Integer[N];
// Extraire progressivement les données du tas max à l'aide de extractMax
// L'ordre d'extraction doit être du plus grand au plus petit
for( int i = 0 ; i < N ; i ++ ){
arr[i] = heapShiftDown.extractMax();
System.out.print(arr[i] + " ");
}
// S'assurer que le tableau arr est trié du plus grand au plus petit
for( int i = 1 ; i < N ; i ++ )
assert arr[i-1] >= arr[i];
}
}