Insert Extract_Min n-mal Sortierte Listen O(n) O(1) O(n²) Heaps O(log n) O(log n) O(n log n) Unsortierte Listen O(1) O(n) O(n²)
Aus der Tabelle ergibt sich, dass Listen entweder beim Einfügen
oder beim Löschen, je nach Listentyp, sehr langsam bzw. sehr
schnell sind.
Heaps bilden von der Geschwindigkeit her einen Mittelweg.
Bei der Verwaltung von n Elementen sind sie deutlich schneller als beide Listentypen.