So verstehen Sie segmentierte Binomialhaufen, die in Reinfunktionalen Datenstrukturen beschrieben sind

8

In Kapitel 6.3.1 der Arbeit Reinfunktionale Datenstrukturen heißt es:

  

Dann, wenn wir einen neuen Baum aus einem neuen Element und einem Segment erstellen   von Bäumen der Ränge 0 ... r-1 vergleichen wir einfach das neue Element mit dem   erste Wurzel in dem Segment (d. h. die Wurzel des Baums mit Rang 0). Das   kleineres Element wird zur neuen Wurzel und das größere Element wird   der Rang 0 Kind der Wurzel.

  1. T0 'ist der neue Baum hat den Rang 0
  2. T0..T (r-1) sind die ursprünglichen Bäume Rang 0 bis r-1
  3. Das kleinere Element wird zum neuen Stamm und das größere Element wird zum Rang 0 Kind des Stamms

Die Frage ist, dass Schritt 3 zu zwei Rang 1-Bäumen führt, was im Konflikt mit den Binomialhaufen steht.

Missverständnis ich?

    
wenlong 23.11.2011, 05:50
quelle

1 Antwort

4

Wir erstellen einen Baum vom Rang r. Die Struktur eines Baumes vom Rang r ist ein Wurzelknoten mit r Kindern der Ränge 0..r-1.

Was der von Ihnen zitierte Teil bedeutet, ist dies.

  1. Wenn wir ein neues Element x erhalten, vergleichen wir es mit dem Element in T0
  2. Wir erstellen einen neuen Baum T0 'mit Rang 0, der das größere der beiden verglichenen Elemente enthält
  3. Wir erzeugen einen neuen Knoten T, der das kleinere der beiden verglichenen Elemente und mit T0 ', T1, T2 ... T (r-1) als untergeordnete Elemente
    4. enthält

Nun ist T ein Binomialbaum vom Rang r und befindet sich in Heap-Reihenfolge.

    
opqdonut 23.11.2011, 10:20
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Identifizieren nicht verwendeter Klassen / Steuerelemente / Seiten