Ist es irgendie möglich 2 Max heaps in O(log n) zu mergen? normal hat insert ja eine Laufzeit von O(logn). wenn ich jetzt aber n Element aus dem einem heap in den anderen einfüge habe ich ja O(n*logn)?
neinIst es irgendie möglich 2 Max heaps in O(log n) zu mergen?
jawenn ich jetzt aber n Element aus dem einem heap in den anderen einfüge habe ich ja O(n*logn)?
ich soll einen Max heap der ein binärer baum ist mit n Knoten (n=2^m) mit einem max heap mit n-1 = (2^m)-1 mergen. Das aber in O(log n) Mir fällt einfach keine möglichkeit ein wie das in dieser Laufzeit gehen sollO(n+m) ist möglich, wenn man die Arrays merged und dann nochmal den Max-Heap bildet
Die Aussage stimmt in der Form so nicht. Zum einen geht es in O(n+m) was kleiner als n*log n sein kann.Vermutlich, weil das nicht unter n*log n möglich ist...
Vielen Dank schonmal ! Nur leider liegt die Art von Heap bei mir nicht vorDie Aussage stimmt in der Form so nicht. Zum einen geht es in O(n+m) was kleiner als n*log n sein kann.
Und es scheint sogar in O(log(n)) zu gehen, wenn es Binomial Heaps sind: https://stackoverflow.com/questions/1595333/algorithm-for-merging-two-max-heaps bzw. https://en.wikipedia.org/wiki/Binomial_heap#Merge
ich soll einen Max heap der ein binärer baum
Ich bin mir bei balancierten Bäumen nie genau sicher... Aber wir kommen schon noch auf des Rätsels lösung.oder liege ich falsch ein binärer heap ist doch kein binomial Heap?
Das dürfte aber falsch sein. O(n log n) ist nicht O(n).O(n*log n) == O(n).
ich dachte vielleicht liegt es an der Anzahl der Knoten in den zwei Bäumen, weil ein Baum ist vollständig und der andere nicht. Der gemerge Baum hat ja nie eine größere Höhe als der Baum mit 2^m Knoten. Und das es aus diesem Grund in log n funktioniert. Jedoch muss man ja für jedes Element heapify aufrufen also wiederrum n*log nDas dürfte aber falsch sein. O(n log n) ist nicht O(n).
O-Notation und Zeitkomplexität - anschaulich erklärt
Anschauliche Erklärungen mit Beispielen und Diagrammen: O-Notationen für die Komplexitätsklassen O(1), O(log n), O(n), O(n log n), O(n²)www.happycoders.eu
Da kann man den Unterschied auch sehr schön in einer Grtafik sehen.
also die Elemente des Baums mit 2^m -1 Knoten passt genau in die letze Ebene des Baums mit 2^m jedoch sind dann möglicherweise die max heap Eigenschaften verletztich dachte vielleicht liegt es an der Anzahl der Knoten in den zwei Bäumen, weil ein Baum ist vollständig und der andere nicht. Der gemerge Baum hat ja nie eine größere Höhe als der Baum mit 2^m Knoten. Und das es aus diesem Grund in log n funktioniert. Jedoch muss man ja für jedes Element heapify aufrufen also wiederrum n*log n
wichtig nochmal zu sagen meine beiden Max heaps sind nicht als Array gespeichert sondern als Binärbaum
Da hast du recht.Das dürfte aber falsch sein. O(n log n) ist nicht O(n).
553: /**
554: * Copies all elements of the given map into this TreeMap. If this map
555: * already has a mapping for a key, the new mapping replaces the current
556: * one.
557: *
558: * @param m the map to be added
559: * @throws ClassCastException if a key in m is not comparable with keys
560: * in the map
561: * @throws NullPointerException if a key in m is null, and the comparator
562: * does not tolerate nulls
563: */
564: public void putAll(Map<? extends K, ? extends V> m)
565: {
566: Iterator itr = m.entrySet().iterator();
567: int pos = m.size();
568: while (--pos >= 0)
569: {
570: Map.Entry<K,V> e = (Map.Entry<K,V>) itr.next();
571: put(e.getKey(), e.getValue());
572: }
573: }
aber ein max Heap ist doch kein binominal Heap?Man muss jetzt aufpassen - Komplexititätstheorie ist alles, aber nicht trivial.
Nur weil eine TreeMap einen Neuaufbau in O(n log(n)) macht, sagt das erst mal null darüber aus ob ein Merge von Max Heaps nicht trotzdem in O(log n) geht. Wie man ja verlinkt sieht, es bei Binomial Heaps.
Dann kommt noch ein weiteres Problem hinzu - die O-Notation ist ein asymptotische Laufzeitbeschreibung.
So ist in der O-Notation O(n log(n)) besser als O(n). Aber wenn die Faktoren wie folgt sind:
0.00001 *n*log(n) vs. 5.000.000 * n ist in der Praxis für alle relevanten n der O(n log(n)) Algorithmus besser.
Das nächste Problem ist dann bei Datenstrukturen, die mehrere Operationen anbieten - da ist je nach konkreter Datenstruktur immer ein Tradeoff. Reduziere ich die Laufzeit bei der einen Operation erhöhe ich sie bei der anderen.
Gehen wir das mal theoretisch durch:wichtig nochmal zu sagen meine beiden Max heaps sind nicht als Array gespeichert sondern als Binärbaum