Montículo indexado y su optimización
1. Concepto e introducción
El montículo indexado es una optimización de la estructura de datos del montículo.
El montículo indexado utiliza un nuevo array de tipo int para almacenar información de índices.
En comparación con el montículo, las ventajas son las siguientes:
- Optimiza el costo de intercambio de elementos.
- La posición de los datos agregados es fija, lo que facilita su búsqueda.
2. Instrucciones de aplicación
Si los elementos almacenados en el montículo son grandes, intercambiarlos consumirá mucho tiempo. En este caso, se puede utilizar la estructura de datos de montículo indexado como alternativa. El montículo almacena los índices del array, y las operaciones correspondientes se realizan sobre los índices.
3. Diagrama de estructura
Necesitamos modificar la implementación del código del montículo anterior y cambiar a la idea de operar directamente con índices. Primero, en el constructor se añade el atributo de array de índices 'indexes'.
protected int[] indexes; // Índices en el montículo indexado máximo
protected int count;
protected int capacity;
El constructor correspondiente se ajusta para agregar la inicialización del array de índices.
public IndexMaxHeap(int capacity){
data = (T[])new Comparable[capacity+1];
indexes = new int[capacity+1];
count = 0;
this.capacity = capacity;
}
...
Ajuste la operación de inserción: el elemento agregado al array 'indexes' es el índice real del array 'data'.indexes[count+1] = i。
// Inserta un nuevo elemento en el montículo indexado máximo, el índice del nuevo elemento es i y el elemento es item
// El i pasado al usuario está indexado desde 0
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);
}
...
Ajuste la operación shift up: se compara el tamaño de los datos del nodo padre en el array 'data', por lo que debe expresarse comodata[index[k/2]] < data[indexs[k]]intercambia los índices del array 'index'. El array 'data' no sufre ninguna modificación. Lo mismo ocurre con shift down.
// k es el índice del montículo
// En el montículo indexado, la comparación de datos se realiza según el tamaño de 'data', pero en realidad se operan los índices
private void shiftUp(int k){
while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0 ){
swapIndexes(k, k/2);
k /= 2;
}
}
...
Al extraer un elemento del montículo indexado, el elemento más grande es el elemento raíz.data[index[1]]de los datos, y luego intercambiar las posiciones de los índices para realizarshift downla operación.
public T extractMax(){
assert count > 0;
T ret = data[indexes[1]];
swapIndexes( 1 , count );
count --;
shiftDown(1);
return ret;
}
...
También se puede obtener directamente el valor del índice del array 'data' del valor máximo.
// Obtiene el índice del elemento superior del montículo indexado máximo
public int extractMaxIndex(){
assert count > 0;
int ret = indexes[1] - 1;
swapIndexes( 1 , count );
count --;
shiftDown(1);
return ret;
}
...
Modificar los datos en la posición del índice.
// Modifica el elemento con índice i en el montículo indexado máximo a newItem
public void change( int i , Item newItem ){
i += 1;
data[i] = newItem;
// Encuentra indexes[j] = i, j representa la posición de data[i] en el montículo
// Luego shiftUp(j), y después shiftDown(j)
for( int j = 1 ; j <= count ; j ++ )
if( indexes[j] == i ){
shiftUp(j);
shiftDown(j);
return;
}
}
...
4. Código de ejemplo en Java
Descargar paquete de código fuente:Download
Código del archivo src/ejemplo/heap/IndexMaxHeap.java:
import java.util.Arrays;
/**
* Montículo indexado
*/
// Montículo indexado máximo, idea: los elementos se comparan por los datos 'data', el intercambio de elementos es por índices
public class IndexMaxHeap<T extends Comparable> {
protected T[] data; // Datos en el montículo indexado máximo
protected int[] indexes; // Índices en el montículo indexado máximo
protected int count;
protected int capacity;
// Constructor, construye un montículo vacío que puede contener 'capacity' elementos
public IndexMaxHeap(int capacity){
data = (T[])new Comparable[capacity+1];
indexes = new int[capacity+1];
count = 0;
this.capacity = capacity;
}
// Devuelve el número de elementos en el montículo indexado
public int size(){
return count;
}
// Devuelve un valor booleano que indica si el montículo indexado está vacío
public boolean isEmpty(){
return count == 0;
}
// Inserta un nuevo elemento en el montículo indexado máximo, el índice del nuevo elemento es i y el elemento es item
// El i pasado al usuario está indexado desde 0
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);
}
// Toma el elemento superior del montículo indexado máximo, es decir, el dato más grande almacenado en el montículo indexado
public T extractMax(){
assert count > 0;
T ret = data[indexes[1]];
swapIndexes( 1 , count );
count --;
shiftDown(1);
return ret;
}
// Obtiene el índice del elemento superior del montículo indexado máximo
public int extractMaxIndex(){
assert count > 0;
int ret = indexes[1] - 1;
swapIndexes( 1 , count );
count --;
shiftDown(1);
return ret;
}
// Obtiene el elemento superior del montículo indexado máximo
public T getMax(){
assert count > 0;
return data[indexes[1]];
}
// Obtiene el índice del elemento superior del montículo indexado máximo
public int getMaxIndex(){
assert count > 0;
return indexes[1]-1;
}
// Obtiene el elemento con índice i en el montículo indexado máximo
public T getItem( int i ){
assert i + 1 >= 1 && i + 1 <= capacity;
return data[i+1];
}
// Modifica el elemento con índice i en el montículo indexado máximo a newItem
public void change( int i , T newItem ){
i += 1;
data[i] = newItem;
// Encuentra indexes[j] = i, j representa la posición de data[i] en el montículo
// Luego shiftUp(j), y después shiftDown(j)
for( int j = 1 ; j <= count ; j ++ )
if( indexes[j] == i ){
shiftUp(j);
shiftDown(j);
return;
}
}
// Intercambia los índices i y j en el montículo indexado
private void swapIndexes(int i, int j){
int t = indexes[i];
indexes[i] = indexes[j];
indexes[j] = t;
}
//********************
//* Funciones auxiliares principales del montículo indexado máximo
//********************
// k es el índice del montículo
// En el montículo indexado, la comparación de datos se realiza según el tamaño de 'data', pero en realidad se operan los índices
private void shiftUp(int k){
while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0 ){
swapIndexes(k, k/2);
k /= 2;
}
}
// En el montículo indexado, la comparación de datos se realiza según el tamaño de 'data', pero en realidad se operan los índices
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;
}
}
// Probar 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) );
}
}
En la modificación de la posición del índice anterior, usamos un recorrido para buscar la posición del índice, lo cual no es eficiente. Podemos optimizarlo aún más, manteniendo un conjunto dereverse[i]arrays que representan la posición del índice i en indexes (el montículo), reduciendo la complejidad temporal de la búsqueda a O(1).
Tiene las siguientes propiedades:
indexes[i] = j reverse[j] = i indexes[reverse[i]] = i reverse[indexes[i]] = iOtras extensiones