heap
-
hallo
weiß jemand warum man zum suchen die funktion make_heap oder sort_heap geschrieben hat wenn es eine funktion sort gibt
-
Ich denke mal, weil sort aus der Standard lib kommt und die make_heap und sort_heap nicht... ?
Wenn´s falsch ist, ich hab nur laut gedacht x)
Lg Mentras
-
sort_heap hat imho ne andere komplexität im worst-case als das normale sort...
dort sollten die unterschiede deutlich werden:
http://www.cplusplus.com/reference/falls du dann das Bedürfnis haben solltest, deine Erkenntnisse hier noch mal zusammen zufassen.. niemand hält dich davon ab
bb
edit:
komplexität:
make_heap:At most, (3*(last-first)) comparisons.
sort_heap:At most, NlogN comparisons, where N is (last-first).
sort: `Approximately N*logN comparisons on average (where N is last-first).In the worst case, up to N2, depending on specific sorting algorithm used by library implementation.`
-
hat des was auch mit der speicherverwaltung heap und stack zu tun
-
hansigarten2 schrieb:
hat des was auch mit der speicherverwaltung heap und stack zu tun
Nein, nicht wirklich.
-
-
thx habs
-
hansigarten2 schrieb:
weiß jemand warum man zum suchen die funktion make_heap oder sort_heap geschrieben hat wenn es eine funktion sort gibt
Heaps sind eine spezielle Art von Datenstruktur, die unter anderem durch Arrays modelliert werden kann (darauf basieren die
*_heap-Funktionen der Standardbibliothek).std::sort()hingegen kann auf sequentielle Container angewandt werden, die Random Access unterstützen, und erzeugt eine (linear) sortierte Folge.
