Tri par tas de base
1. Concept et introduction
Le tri par tas est un algorithme de tri conçu en utilisant la structure de données tas.
Un tas est une structure qui approxime un arbre binaire complet et satisfait simultanément la propriété de tas : c'est-à-dire que la clé ou l'indice d'un nœud enfant est toujours inférieur (ou supérieur) à celui de son nœud parent.
II. Instructions d'application
Notre processus précédent de construction d'un tas consistait à insérer les données une par une dans le tas en appelant la méthode insert à l'aide de shift up ; la complexité temporelle de cet algorithme estO(nlogn), le processus de construction d'un tri par tas introduit dans cette section est appeléHeapify, la complexité temporelle de l'algorithme estO(n)。
III. Diagramme du processus
Un arbre binaire complet possède une propriété importante : l'indice du premier nœud non-feuille estn/2la valeur d'indice obtenue en prenant la partie entière, oùnest le nombre d'éléments (en supposant que les indices de tableau commencent à 1).
La position à l'indice 5 est le premier nœud non-feuille. À partir de celui-ci, nous avançons un par un, en effectuant l'opération de descente sur chaque élément en tant que nœud racine afin de satisfaire la propriété du tas max.
Après l'opération de descente à l'indice 5, 22 et 62 échangent leurs positions.
Effectuer l'opération de descente sur l'élément à l'indice 4.
Effectuer l'opération de descente sur l'élément à l'indice 3.
Effectuer l'opération de descente sur l'élément à l'indice 2.
Enfin, effectuez l'opération de descente sur le nœud racine, et l'ensemble du processus de tri par tas est terminé.
IV. Exemple de code Java
Téléchargement du paquet de code source :Télécharger
Code du fichier src/example/heap/Heapify.java :
import example.sort.SortTestHelper;
/**
* Utiliser heapify pour effectuer le tri par tas
*/
public class Heapify<T extends Comparable> {
protected T[] data;
protected int count;
protected int capacity;
// Constructeur, crée un tas max à partir d'un tableau donné
// Le processus de construction du tas a une complexité temporelle O(n)
public Heapify(T arr[]){
int n = arr.length;
data = (T[])new Comparable[n+1];
capacity = n;
for( int i = 0 ; i < n ; i ++ )
data[i+1] = arr[i];
count = n;
// Commencer à partir du premier élément qui n'est pas un nœud feuille
for( int i = count/2 ; i >= 1 ; i -- )
shiftDown(i);
}
// 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;
}
}
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;
}
}
// Tester heapify
public static void main(String[] args) {
int N = 100;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
Heapify<Integer> heapify = new Heapify<Integer>(arr);
// Extraire progressivement les données dans heapify à 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] = heapify.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];
}
}