Lista de matrices ordenadas en Java

Uso java.util.PriorityQueue.

Echa un vistazo a SortedList

Esta clase implementa una lista ordenada. Se construye con un comparador que puede comparar dos objetos y ordenar los objetos en consecuencia. Cuando agrega un objeto a la lista, se inserta en el lugar correcto. Los objetos que son iguales según el comparador, estarán en la lista en el orden en que se agregaron a esta lista. Agregue solo objetos que el comparador pueda comparar.

Cuando la lista ya contiene objetos que son iguales según el comparador, el nuevo objeto se insertará inmediatamente después de estos otros objetos.

Puede intentar Guayaba del TreeMultiSet.

 Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
 System.out.println(ms);

Las listas normalmente conservan el orden en el que se agregan los elementos. ¿Necesita definitivamente una lista , o un conjunto ordenado (p.ej. TreeSet<E>) ¿estar bien para ti? Básicamente, ¿necesita conservar duplicados?

El enfoque de Aioobe es el camino a seguir. Sin embargo, me gustaría sugerir la siguiente mejora sobre su solución.

class SortedList<T> extends ArrayList<T> {

    public void insertSorted(T value) {
        int insertPoint = insertPoint(value);
        add(insertPoint, value);
    }

    /**
     * @return The insert point for a new value. If the value is found the insert point can be any
     * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.).
     */
    private int insertPoint(T key) {
        int low = 0;
        int high = size() - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = (Comparable<T>) get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else {
                return mid; // key found
            }
        }

        return low;  // key not found
    }
}

La solución de Aioobe se vuelve muy lenta cuando se usan listas grandes. Usar el hecho de que la lista está ordenada nos permite encontrar el punto de inserción para nuevos valores utilizando la búsqueda binaria.

También usaría la composición sobre la herencia, algo así como

SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Podría ser un poco demasiado pesado para usted, pero GlazedLists tiene un SortedList que es perfecto para usar como modelo de una tabla o JList

Puede subclase ArrayList, y llamar a Colecciones.ordenar (esto) después de que se agrega cualquier elemento - usted tendría que anular dos versiones de add, y dos de addAll, para hacer esto.

El rendimiento no sería tan bueno como una implementación más inteligente que inserta elementos en el lugar correcto, pero haría el trabajo. Si la adición a la lista es rara, el costo amortizado sobre todas las operaciones en la lista debe ser bajo.

Creo que la elección entre SortedSets/Lists y 'normal' sortable collections depende, si necesita ordenar solo para fines de presentación o en casi todos los puntos durante el tiempo de ejecución. Usar una colección ordenada puede ser mucho más caro porque la ordenación se realiza cada vez que se inserta un elemento.

Si no puede optar por una colección en el JDK, puede echar un vistazo a Apache Commons Collections

Dado que las implementaciones actualmente propuestas que implementan una lista ordenada al romper la API de Colección, tienen una implementación propia de un árbol o algo similar, era curioso cómo se desempeñaría una implementación basada en el mapa de árbol. (Especialy desde el TreeSet hace base en TreeMap, demasiado)

Si alguien también está interesado en eso, puede sentirse libre de investigarlo:

Lista de árboles

Es parte de la biblioteca core , puede agregarla a través de La dependencia de Maven, por supuesto. (Licencia Apache)

Actualmente la implementación parece compararse bastante bien en el mismo nivel que el guava SortedMultiSet y con el TreeList de la biblioteca Apache Commons.

Pero estaría feliz si más que solo yo probara la implementación para estar seguro de que no me perdí algo importante.

Saludos cordiales!

Yo tenía el mismo problema. Así que tomé el código fuente de Java.útil.TreeMap and wrote IndexedTreeMap. Implementa mi propio IndexedNavigableMap :

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

La implementación se basa en actualizar los pesos de los nodos en el árbol rojo-negro cuando se cambia. El peso es el número de nodos hijos debajo de un nodo dado, más uno mismo. Por ejemplo, cuando un árbol se gira a la izquierda:

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

UpdateWeight simplemente actualiza los pesos hasta la raíz:

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

Y cuando necesitamos encontrar el elemento por índice aquí es la implementación que usa pesos:

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

También es muy útil encontrar el índice de una clave:

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    index += getWeight(e.left);

    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

Puedes encontrar el resultado de este trabajo en http://code.google.com/p/indexed-tree-map /

TreeSet/TreeMap (así como sus contrapartes indexadas del proyecto indexed-tree-map) no permiten claves duplicadas , puede usar 1 clave para una matriz de valores. Si necesita un SortedSet con duplicados use TreeMap con valores como matrices. Yo haría eso.