welche Datenstruktur?
-
Ich brauche eine Datenstruktur, in die ich beliebig viele Elemenete reinstecken und das "kleinste" Element herausholen kann.
Gibts da was besseres als eine verkettete Liste, in die ich die Elemente einsortiere?
-
nö
-
Datenbank ?
-
Was hältst du von std::priority_queue aus <queue>? Die sortiert das automatisch in einen vector ein... vielleicht nicht effizient, aber immerhin komfortabel
-
Wie wär's mit nem Baum?
Einfügen geht in O(log n), kleinstes Element kriegt man in O(1) hin, löschen ebenfalls in O(log n), gewöhnlicher Zugriff kostest halt wieder O(log n).
Kommt drauf an, was Du wie oft brauchst. bei list/vector/deque ist das einfügen halt relativ teuer.
MfG Jester
-
in der fachliteratur redet man oft von einem heap.
-
Also ich muss oft Elemente einfügen, und genauso oft auf das kleinste Element zugreifen und es löschen, zugriff auf andere Elemente ausser dem kleinsten brauch ich garnicht. Die Anzahl der Element kann sehr stark schwanken, die Elemente werden schon grob sortiert eingefügt (sie kommen aus verschiedenen quellen, von denen die meisten sortiert sind).
Ich glaub die Menge der Elemente ist i.d.R. überschaubar (bin mir da aber nicht ganz sicher). Deshalb tendiere ich im Moment zu einer doppelt verketteten Liste, die Elemente sortiere ich dann von hinten ein. Oder wie soll denn so ein Baum aussehen?
-
google: heap data structure
gibt als zweiten link: what is a heap
-
Ist "heap" nicht einfach ein Ausdruck für Freispeicher?
(also gewissermaßen das Gegenstück zu "stack")gruß,
walker
-
"Heap" hat mehrere Bedeutungen. Hier geht es wohl um die Datenstruktur Heap. Das ist ein spezieller Baum.