Tas indexé et son optimisation
1. Concept et introduction
Le tas indexé est une optimisation de la structure de données du tas.
Le tas indexé utilise un nouveau tableau d'int pour stocker les informations d'index.
Comparé aux tas, les avantages sont les suivants :
- Optimise le coût d'échange des éléments.
- La position des données ajoutées est fixe, ce qui facilite la localisation.
II. Instructions d'applicabilité
Si les éléments stockés dans le tas sont volumineux, leur échange consomme beaucoup de temps. Dans ce cas, la structure de données de tas d'indices peut être utilisée comme substitut ; le tas stocke les indices du tableau, et nous manipulons les indices.
III. Schéma de structure
Nous devons modifier l'implémentation précédente du tas et passer à l'approche consistant à opérer directement sur les indices. Tout d'abord, ajoutez la propriété de tableau d'indices "indexes" au constructeur.
protected int[] indexes; // Indices dans le tas d'indices maximum
protected int count;
protected int capacity;
Ajustez le constructeur en conséquence en ajoutant l'initialisation du tableau d'indices.
public IndexMaxHeap(int capacity){
data = (T[])new Comparable[capacity+1];
indexes = new int[capacity+1];
count = 0;
this.capacity = capacity;
}
...
Ajustez l'opération d'insertion : les éléments ajoutés au tableau indexes sont les indices du tableau de données réel.indexes[count+1] = i。
// Insérer un nouvel élément dans le tas max d'indices. L'indice du nouvel élément est i, et l'élément est item
// Le i passé est indexé à partir de 0 du point de vue de l'utilisateur
public void insert(int i, Item item){
assert count + 1 <= capacity;
assert i + 1 >= 1 && i + 1 <= capacity;
i += 1;
data[i] = item;
indexes[count+1] = i;
count ++;
shiftUp(count);
}
...
Ajustez l'opération de remontée : la comparaison est basée sur la taille des données du nœud parent dans le tableau data, donc elle doit être exprimée commedata[index[k/2]] < data[indexs[k]]en échangeant les indices dans le tableau indexes, ce qui n'entraîne aucun changement dans le tableau data ; il en va de même pour la descente (shift down).
// k est l'indice dans le tas
// Dans le tas d'indices, les comparaisons sont basées sur la taille des données, mais les opérations réelles portent sur les indices
private void shiftUp(int k){
while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0 ){
swapIndexes(k, k/2);
k /= 2;
}
}
...
Lors de l'extraction d'un élément du tas d'indices, le plus grand élément est l'élément racine.data[index[1]]dans les données, puis échangez les positions d'indices pour continuer.shift downopération.
public T extractMax(){
assert count > 0;
T ret = data[indexes[1]];
swapIndexes( 1 , count );
count --;
shiftDown(1);
return ret;
}
...
Vous pouvez également récupérer directement l'index du tableau data correspondant à la valeur maximale.
// Extraire l'index de l'élément au sommet du tas d'indices maximal
public int extractMaxIndex(){
assert count > 0;
int ret = indexes[1] - 1;
swapIndexes( 1 , count );
count --;
shiftDown(1);
return ret;
}
...
Modification des données à une position d'index
// Modifier l'élément d'index i dans le tas d'indices maximal en newItem
public void change( int i , Item newItem ){
i += 1;
data[i] = newItem;
// Trouver indexes[j] = i, où j représente la position de data[i] dans le tas
// Ensuite shiftUp(j), puis shiftDown(j)
for( int j = 1 ; j <= count ; j ++ )
if( indexes[j] == i ){
shiftUp(j);
shiftDown(j);
return;
}
}
...
IV. Exemple de code Java
Téléchargement du paquet source :Télécharger
Code dans src/example/heap/IndexMaxHeap.java :
import java.util.Arrays;
/**
* Tas d'indices
*/
// Tas d'indices max, idée : les comparaisons utilisent les valeurs des données, mais les échanges se font sur les indices
public class IndexMaxHeap<T extends Comparable> {
protected T[] data; // Données dans le tas d'indices maximum
protected int[] indexes; // Indices dans le tas d'indices maximum
protected int count;
protected int capacity;
// Constructeur, construit un tas vide pouvant contenir capacity éléments
public IndexMaxHeap(int capacity){
data = (T[])new Comparable[capacity+1];
indexes = new int[capacity+1];
count = 0;
this.capacity = capacity;
}
// Renvoie le nombre d'éléments dans le tas d'indices
public int size(){
return count;
}
// Renvoie une valeur booléenne indiquant si le tas d'indices est vide
public boolean isEmpty(){
return count == 0;
}
// Insérer un nouvel élément dans le tas max d'indices. L'indice du nouvel élément est i, et l'élément est item
// Le i passé est indexé à partir de 0 du point de vue de l'utilisateur
public void insert(int i, T item){
assert count + 1 <= capacity;
assert i + 1 >= 1 && i + 1 <= capacity;
i += 1;
data[i] = item;
indexes[count+1] = i;
count ++;
shiftUp(count);
}
// Extrait l'élément au sommet du tas d'indices max, c'est-à-dire la donnée maximale stockée dans le tas d'indices
public T extractMax(){
assert count > 0;
T ret = data[indexes[1]];
swapIndexes( 1 , count );
count --;
shiftDown(1);
return ret;
}
// Extraire l'index de l'élément au sommet du tas d'indices maximal
public int extractMaxIndex(){
assert count > 0;
int ret = indexes[1] - 1;
swapIndexes( 1 , count );
count --;
shiftDown(1);
return ret;
}
// Obtenir l'élément au sommet du tas d'index maximum
public T getMax(){
assert count > 0;
return data[indexes[1]];
}
// Obtenir l'index de l'élément au sommet du tas d'index maximum
public int getMaxIndex(){
assert count > 0;
return indexes[1]-1;
}
// Obtenir l'élément ayant l'index i dans le tas d'index maximum
public T getItem( int i ){
assert i + 1 >= 1 && i + 1 <= capacity;
return data[i+1];
}
// Modifier l'élément d'index i dans le tas d'indices maximal en newItem
public void change( int i , T newItem ){
i += 1;
data[i] = newItem;
// Trouver indexes[j] = i, où j représente la position de data[i] dans le tas
// Ensuite shiftUp(j), puis shiftDown(j)
for( int j = 1 ; j <= count ; j ++ )
if( indexes[j] == i ){
shiftUp(j);
shiftDown(j);
return;
}
}
// Échanger les indices i et j dans le tas d'index
private void swapIndexes(int i, int j){
int t = indexes[i];
indexes[i] = indexes[j];
indexes[j] = t;
}
//********************
//* Fonctions auxiliaires principales du tas d'index max
//********************
// k est l'indice dans le tas
// Dans le tas d'indices, les comparaisons sont basées sur la taille des données, mais les opérations réelles portent sur les indices
private void shiftUp(int k){
while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0 ){
swapIndexes(k, k/2);
k /= 2;
}
}
// Dans le tas d'indices, les comparaisons sont basées sur la taille des données, mais les opérations réelles portent sur les indices
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k;
if( j+1 <= count && data[indexes[j+1]].compareTo(data[indexes[j]]) > 0 )
j ++;
if( data[indexes[k]].compareTo(data[indexes[j]]) >= 0 )
break;
swapIndexes(k, j);
k = j;
}
}
// Test IndexMaxHeap
public static void main(String[] args) {
int N = 1000000;
IndexMaxHeap<Integer> indexMaxHeap = new IndexMaxHeap<Integer>(N);
for( int i = 0 ; i < N ; i ++ )
indexMaxHeap.insert( i , (int)(Math.random()*N) );
}
}
Dans la modification de position d'index ci-dessus, nous avons utilisé un parcours pour trouver la position de l'index, ce qui est inefficace. Nous pouvons l'optimiser davantage en maintenant un ensemble dereverse[i]tableaux qui représentent la position de l'index i dans indexes (le tas), réduisant la complexité temporelle de la recherche à O(1).
Il a les propriétés suivantes :
indexes[i] = j reverse[j] = i indexes[reverse[i]] = i reverse[indexes[i]] = iautres extensions