Zitat von
Meflin:
Zitat von
alzaimar:
Woher weiss man das?
Indem man es beim Einfügen schon sortiert hält
Das ist dann auch langsamer als mal eben in einem unsortierten Array zu suchen
Zitat von
Meflin:
Gesetz dem äußerst unwahrscheinlichen Fall, dass man tatsächlich nur ein allereinziges Mal das Minimum haben will
Wieso sollte ich öfter das Minimum eines Arrays ermitteln? Ändern tut es sich doch eh nicht
Nun zur Theorie:
Wenn ich eine listenartige Datenstruktur inklusive Kenntnis des kleinsten/größten Elements benötige, werde ich meine Basisstruktur u.a. danach aussuchen, ob ich die Elemente sortiert benötige. Wenn nicht, und Löschoperationen selten sind, dürfte eine unsortierte Liste eine gute Wahl darstellen. Ansonsten empfehle ich eine Skiplist, die hier im Gegensatz zu einer sortierten Liste stets optimale Ergebnisse liefert. So sind so gut wie alle Operationen näherungsweise O(1), wohingegen eine sortierte Liste beim Einfügen und Löschen einen Aufwand O(n) und beim Suchen O(log n) aufweist. Nicht besonders, wenn Du mich fragst.