Java Heap-Implementierung / Avoid too much sorting II

Im Artikel Avoid too much sorting habe ich ja schon kurz skizziert, dass man es generell vermeiden sollte seine Daten unnötig oft zu sortieren, weil das einfach (je nachdem wie oft der entsprechende Code aufgerufen wird) ziemlich in die Rechenzeit gehen kann.

Manchmal muss man seine Daten aber eben sortiert halten. – Dann sollte man sich aber überlegen, ob man wirklich die ganzen Daten sortieren muss, oder ob es nicht einfach reicht, immer das kleinste/größte Element einer Menge zu bekommen. Ein gutes Beispiel ist zum Beispiel der altbekannte Dijkstra-Algorithmus. Dort benötigt man in jeder Iteration z.B. den Weg mit den bisher kleinsten Kosten.

Das schreit ja schon nach Sortieren. Bzw. eigentlich sollte einem da gleich die Heap-Datenstruktur einfallen, da dort alle Operaionen maximal in O(log n) erledigt sind, und nicht (wie beim Sortieren) in bis zu O(n²). Das schöne daran ist, dass es das in Java auch schon gibt, da heißt es nur nicht Heap (da man dabei vermutlich zu sehr an die Speicherverwaltung denken könnte), sondern PriorityQueue.

Wenn man jetzt aber Objekte sortieren will die nicht per se Comparable sind, benötigt man noch eine kleine Comparator-Implementierung mit einem SimpleEntry, damit man einem beliebigem Objekt auch seine Kosten zuweisen kann. Klingt jetzt recht aufwändig – ist es aber bei weitem nicht:

import java.util.AbstractMap.SimpleEntry;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Test {
    public static void main(String[] args) {
        PriorityQueue<SimpleEntry> heap =
                new PriorityQueue<SimpleEntry>(10, new FooCmp());
        heap.add(new SimpleEntry(1d, new Foo(1)));
        heap.add(new SimpleEntry(5d, new Foo(2)));
        heap.add(new SimpleEntry(2d, new Foo(3)));
        while (!heap.isEmpty()) {
            System.out.println(heap.poll().getValue().i);
        }
    }
}

class FooCmp implements Comparator<SimpleEntry> {
    @Override
    public int compare(SimpleEntry o1, SimpleEntry o2) {
        return Double.compare(o1.getKey(), o2.getKey());
    }
}

class Foo {
    int i;
    Foo(int i) { this.i = i; }
}