Sort TreeMap

com um TreeMap você não pode, não estou dizendo que é impossivel mas isso desafia a especificação do SortedMap
http://docs.oracle.com/javase/6/docs/api/java/util/SortedMap.html

The map is ordered according to the natural ordering of its keys, or by a Comparator typically provided at sorted map creation time.

TreeMap ordena suas entradas pela ordenação natural das chaves.
No seu caso essas chaves são do tipo Integer.
Você até pode fornecer um Comparator para o TreeMap, mas esse Comparator só vai servir para comparar as chaves.

Se essas chaves correspondem à índices, então recomendo utilizar List ao invés de TreeMap.

Com List você pode definir os comparadores abaixo:

static final Comparator<Objeto> ASCENDENTE = new Comparator<Objeto>() {

	@Override
	public int compare(Objeto a, Objeto b) {
		return (int) (a.getValor() - b.getValor());
	}
};

static final Comparator<Objeto> DESCENDENTE = new Comparator<Objeto>() {

	@Override
	public int compare(Objeto a, Objeto b) {
		return (int) (b.getValor() - a.getValor());
	}
};

E ordenar assim:

// ordenação ascendente
Collections.sort(objetos, ASCENDENTE);

ou assim:

// ordenação decendente
Collections.sort(objetos, DESCENDENTE);

Muito Obrigado a todos que ajudaram, então eu precisaria usar o TreeMap mesmo porque o professor queria que tudo tivesse log(N) e com lista não daria certo. Pesquisei para caralho e todas as funçoes que achei faziam praticamente a mesma coisa , transformava em Uma Collections da vida e ordenadava.