Heap Algo - Hilfe bei Übungen aus dem Sedgewick

[Dionysos211]

Hallo,

hab da eine kleine Frage zu Übungen aus dem Sedgewick

Frage 4:

• Welche Positionen können von dem drittgrößten Schlüssel in einem Heap der Größe 32 eingenommen werden?
  
• Welche Positionen können von dem drittkleinsten Schlüssel in einem Heap der Größe 32 nicht eingenommen werden?
  

Aus dem Kapitel 11.5 (Robert Sedgewick: Algorithmen) geht hervor:

Um zum Beispiel einen Heap aus 127 Elementen aufzubauen, ruft die Methode downheap für (64 Heaps der Größe 1), 32 Heaps der Größe 3, 16 Heaps der Größe 7, 8 Heaps der Größe 15, 4 Heaps der Größe 31, 2 Heaps der Größe 63 und einen Heap der Größe 127 auf, so daß im ungünstigsten Falle 64 * 0 + 32 * 1 + 16 * 2 + 8 * 3 + 4 * 4 + 2 * 5 + 1 * 6 = 120 »Übertragungen« (doppelt so viele Vergleiche) benötigt werden. Für M = 2m ist eine obere Schranke für die Anzahl der Vergleiche durch

verstehe ich das jetzt richtig das ich bei der Frage annehmen kann das mit der "Größe" eines Heap dort die Anzahl der Elemente gemeint ist ?

also:

16 Heaps der Größe 1

8 Heaps der Größe 3

4 Heaps der Größe 7

2 Heaps der Größe 15

1 Heap der Größe 31

16 * 0 + 8 * 1 + 4 * 2 + 2 * 3 + 1 * 4 = 26

( den Teil versteh ich leider nicht ganz)

Also mal gedanklich das ganz als Baum vorgestellt, hätte ich links 16 knoten (15+ das letzte Child (Element 32) und rechts 15 Knoten.... dazu + einmal die Wurzel = 32 Elemente.

Somit könnte der 3. größte Schlüssel 17 Positionen inkl. seiner derzeitigen der Wurzel und + das eine Blatt der letzten Knotenebene (Element 32) einnehmen.

Wenn man davon ausgeht das upheap wie downheap auf das element losgelassen wird.

Sollte nur Downheap gehen dann fällt die wurzel weg = 16 Positionen.

das 3. kleinste Element, was auch im rechten Teilbaum wäre, könnte 25 nicht einnehmen.

wenn man davon ausgeht das upheap und downheap losgelassen wird.

Denn es kann durch diese Operationen lediglich 7 Positionen einnehmen

bei 32 möglichen Positionen macht das 25 ...

De linke teilbaum fällt weg (ausgenommen element 32) und vom rechten teilbaum der linke zweig vom 7. größten und 3. Größten Schlüssel...

==========

So wenn das da oben von mir ÜBERHAUPT richtig ist kann man das sicher geschickter erklären... kann mir da wer helfen bitte ?

[Dionysos211]

ok mein erster Denkfehler ist glaub ich das erreichen des letzten Elements vom rechten Teilbaum aus... das haut nicht hin... glaub ich...

[Dionysos211]

Ok ich versuch die Antwort mal neu zu formulieren...

Grundlegende Betrachtung zum gegebenen Heap:

• 32 Elemente
  
• 16 Knoten
  
• 16 Blätter
  
• Tiefe 6
  

Aufgaben Teil a.)

• 3. größter Schlüssel (3. Knoten bzw. 2. Knoten nach der Wurzel)
  
• Aufgabenstellung besagt die vorangegangenen Schlüssel sind größer.
  
• Somit handelt es sich um einen Heap-Max
  
• Aufgrund der Heapbedingung ist anzunehmen das die Folgeelemente kleiner sind.
  

Aufgaben Teil b.)

• 3. kleinster Schlüssel (14. Blatt bzw. linker Nachfolger des 15. Knotens)
  
• Aufgabenstellung besagt die nachfolgenden Schlüssel sind kleiner.
  
• Es ist anzunehmen das es sich auch hier um einen Heap-Max handelt.
  
• Aufgrund der Heapbedingung ist anzunehmen das alle Vorgänger größer sind.
  

Somit finde ich die Aufgabe irgendwie schwer zu zu beantworten, weil somit implizit gesagt wurde das das jeweils beschriebene Element in Aufgabenteil a.) und b.) eigentlich nirgends hin kann da es sich bereits an der richtigen stelle befindet...

Eine gültige alternative Position könnte höchstens der Vaterknoten sein. Da die Heapbedingung an dieser Stelle besagt, dass der Nachfolgeknoten kleiner sein muss oder gleich groß wie das Knotenelement.. was ja an der Stelle der Fall sein könnt bei Aufgabenteil b.)

alles n bischen "strange"... kann mir wer ausm Dilemma helfen ?

Ich finde auch keine Lösung dazu im Netz... -.-

Wenn es wirklich nur ums hochschieben und runterschieben geht, und das auch in einem Schritt bis Ende dann bedeutet das für

Aufgabenteil a.)

+ runterschieben (14)

+ hochschieben (1)

+ sich selbst

= 16 mögliche Positionen

Aufgabenteil b.)

+ runterschieben (0) es ist ein Blatt

+ hochschieben (4)

+ sich selbst

= 5 mögliche Positionen

und nun der Clou da steht j ein nicht also ist die Antwort: Es gibt 27 Positionen die er nicht einnehmen kann (32 gesamt - 5 möglich)

wenn ich abwechselnd up und down heap benutzen könnte dann wären schlichtweg alle Positionen möglich...

boa ... *confused* hoch 3

Bearbeitet 7. Juli 2011 von Dionysos211