Mergen von 2 Max Heaps

[Mariexshhx]

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)?

 

[weihnachtspyramide]

Ist es irgendie möglich 2 Max heaps in O(log n) zu mergen?

nein

wenn ich jetzt aber n Element aus dem einem heap in den anderen einfüge habe ich ja O(n*logn)?

ja

 

[thecain]

O(n+m) ist möglich, wenn man die Arrays merged und dann nochmal den Max-Heap bildet

 

[Mariexshhx]

O(n+m) ist möglich, wenn man die Arrays merged und dann nochmal den Max-Heap bildet

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 soll

 

[weihnachtspyramide]

Vermutlich, weil das nicht unter n*log n möglich ist...

 

[LimDul]

Vermutlich, weil das nicht unter n*log n möglich ist...

Die 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

 

[Mariexshhx]

Die 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

Vielen Dank schonmal ! Nur leider liegt die Art von Heap bei mir nicht vor

 

[thecain]

ich soll einen Max heap der ein binärer baum

 

[Mariexshhx]

oder liege ich falsch ein binärer heap ist doch kein binomial Heap?

 

[weihnachtspyramide]

oder liege ich falsch ein binärer heap ist doch kein binomial Heap?

Ich bin mir bei balancierten Bäumen nie genau sicher... Aber wir kommen schon noch auf des Rätsels lösung.

 

[weihnachtspyramide]

Aus der Wikipedia:



und


Du sagst, du hast einen binären Max-Heap, dann doch O(n*log n) == O(n).

 

[KonradN]

O(n*log n) == O(n).

Das 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.

 

[Mariexshhx]

Das 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.

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 n

wichtig nochmal zu sagen meine beiden Max heaps sind nicht als Array gespeichert sondern als Binärbaum

 

[Mariexshhx]

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 n

wichtig nochmal zu sagen meine beiden Max heaps sind nicht als Array gespeichert sondern als Binärbaum

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 verletzt

 

[weihnachtspyramide]

Mein Verdacht erhärtet sich:

Source for java.util.TreeSet (GNU Classpath 0.95 Documentation)

addAll iteriert ebenfalls über jedes Element.

Das dürfte aber falsch sein. O(n log n) ist nicht O(n).

Da hast du recht.

Why is O(n) better than O( nlog(n) )?

I just came around this weird discovery, in normal maths, n*logn would be lesser than n, because log n is usually less than 1. So why is O(nlog(n)) greater than O(n)? (ie why is nlogn considered to...

stackoverflow.com

Aber der Wikipedia-Eintrag schließt O(n log n) nicht aus...

Edit:

 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:   }

Source for java.util.TreeMap (GNU Classpath 0.95 Documentation)

Zumindest in Java ist es so, dass O(n * log n) benötigt wird. Bin mir nicht sicher, ob der Wikipedia-Eintrag richtig ist.

 

[LimDul]

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.

 

[Mariexshhx]

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.

aber ein max Heap ist doch kein binominal Heap?

 

[weihnachtspyramide]

Bezüglich der Komplexität: Nehmen wir mal an, der tatsächliche Aufwand für einen optimalen Merge-Algorithmus würde 10*n betragen, was schon eine optimistische Schätzung ist. Also pro Element werden nicht mehr als 10 Elementaroperationen für das Einfügen benötigt. Dann würde sich der optimale Algorithmus erst ab 22.000 Elementen "lohnen", also ab dieser Anzahl geringfügig schneller werden:

10*x=x*log(x) - Wolfram|Alpha

Wolfram|Alpha brings expert-level knowledge and capabilities to the broadest possible range of people—spanning all professions and education levels.

www.wolframalpha.com

Ich danke, das könnte mit ein Grund sein, weshalb man in Java einen Algorithmus gewählt hat, der jedes Element einzeln hinzufügt.

BTW: Der Probealarm funktionierte bei mir gerade.

 

[weihnachtspyramide]

wichtig nochmal zu sagen meine beiden Max heaps sind nicht als Array gespeichert sondern als Binärbaum

Gehen wir das mal theoretisch durch:

Angenommen, es gibt n Elemente in Halde A und m Elemente in Halde B. Halde B soll in Halde A eingefügt werden. Weiterhin gelte: (A) Alle Elemente in Halde B sind kleiner als das kleinste Element in Halde A - oder (B) alle Elemente in Halde B sind größer als das größte Element in Halde A.

Für (A) und (B) gilt: Ich vergrößere Halde A um m Elemente. Danach kann ich alle Elemente aus Halde B in O(1) einfügen. Der Aufwand wäre also konstant.

Gilt (A) oder (B) jedoch nicht, so komme ich zumindest nicht umhin, alle Elemente aus Halde B einzeln durchzugehen, und damit in O(m*log(n+m)) einzufügen ... was in etwa O(n) entsprechen sollte (hoffe ich).

Weshalb log(n+m)? Die initiale n-elementige Halde A wächst ja um m Elemente an... Ich benötige also log(n) + log(n+1) + log(n+2) + ... + log(n+m) Operationen, um alle m Elemente einzufügen.

Siehe auch: https://en.wikipedia.org/wiki/Heap_(data_structure)#Comparison_of_theoretic_bounds_for_variants

Deshalb ist die Eingangsfrage, glaube ich, nicht möglich.

 

[weihnachtspyramide]

Hm, könnte es sein, dass das Ganze etwas mit der Stirling-Approximation zu tun hat? Dann bin ich raus.