K-tes Element in einem Heap-Baum

Question

Ich habe einen Heap (implementiert wie ein binärer Baum: Jeder Knoten hat zwei Zeiger auf die Kinder und einen Zeiger auf den Eltern).

Wie kann ich das k-te Element (in einer BFS-Reihenfolge) finden, wenn die Anzahl der Elemente darin angegeben ist? Ich denke, es kann in O (logn) Zeit gemacht werden.

Answer 1

(Ich nehme an "kth Element (in einer BFS-Reihenfolge)", dass Sie das k-te Element aus der Perspektive von oben nach unten bedeuten Von links nach rechts scannen des Eingangs.

Da Sie wissen, dass ein binärer Haufen ein vollständiger Binärbaum ist (außer möglicherweise auf der letzten Ebene), wissen Sie, dass die Form des Baums ein perfekter Binärbaum ist einiger Höhe (enthält 2 ^k Knoten für einige k) mit einer gewissen Anzahl von Knoten von links nach rechts gefüllt. Eine wirklich nette Eigenschaft dieser Bäume tritt auf, wenn Sie die Nummern der Knoten in einem Bild schreiben, eine Indizierung der Werte:

     1 
      2    3 
     4  5  6  7 
     8 9 10 11 12 13 14 15 

Beachten Sie, dass jede Schicht mit einem Knoten beginnt, die eine Zweierpotenz ist. Also lassen Sie uns annehmen, hypothetisch, dass Sie die Nummer 13. Die größte Leistung von zwei nicht größer als 13 ist 8, sehen wollten, damit wir wissen, dass 13 in der Reihe

8 9 10 11 12 13 14 15 

Wir diese können jetzt erscheinen Wissen, um den Weg von 13 zurück bis zur Wurzel des Baumes zurückzuentwickeln. Wir wissen zum Beispiel, dass 13 in der zweiten Hälfte der Zahlen in dieser Zeile steht, was bedeutet, dass 13 zum rechten Teilbaum der Wurzel gehört (wenn er zum linken Teilbaum gehört, dann wären wir im Teilbaum enthalten) Diese 8, 9, 10 und 11) bedeutet, dass wir direkt von der Wurzel gehen und die Hälfte der Zahlen werfen

12 13 14 15 

wir sind am Knoten 3 im Baum jetzt zu bekommen. Gehen wir also nach links oder rechts? Nun, 13 ist in der ersten Hälfte dieser Zahlen, so dass wir an dieser Stelle wissen, dass wir in den linken Teilbaum von Knoten 3 absteigen müssen. Dies bringt uns zu Knoten 6, und jetzt sind wir mit der ersten Hälfte der Zahlen:

12 13 

13 in der rechten Hälfte dieser Knoten ist, sollten wir nach rechts, wir nehmen so absteigen 13. Und voila zum Knoten! War da!

Also, wie hat dieser Prozess funktioniert? Nun, es gibt einen wirklich, wirklich süßen Trick, den wir verwenden können. Lassen Sie uns den gleichen Baum schreiben wir oben hatten, aber in binär:

1. die Schicht Finden enthält:

        0001 
         0010     0011 
        0100  0101  0110  0111 
       1000 1001 1010 1011 1100 1101 1110 1111 
              ^^^^ 
   

   Ich habe die Position des Knotens 13. Unser Algorithmus arbeitet in der folgenden Art und Weise darauf hingewiesen, der Knoten.

2. am Knoten in Frage Während nicht:
   1. Wenn der Knoten in seiner in der ersten Hälfte der Schicht ist, nach links bewegen und die rechte Hälfte des Bereichs wegzuwerfen.
   2. Wenn sich der Knoten in der zweiten Hälfte der Ebene befindet, in der er sich befindet, bewegen Sie sich nach rechts und werfen Sie die linke Hälfte des Bereichs weg.

nachdenken lassen über das, was das bedeutet, in binär.Das Finden der Ebene, die den Knoten enthält, ist entspricht dem Finden des höchstwertigen Bits, das in der Nummer festgelegt ist. In 13, das eine Binärdarstellung 1101 aufweist, ist das MSB das 8-Bit. Das bedeutet, dass wir uns in der Ebene befinden, die mit acht beginnt.

Wie können wir feststellen, ob wir im linken Teilbaum oder im rechten Teilbaum sind? Nun, um das zu tun, müssten wir sehen, ob wir in der ersten Hälfte dieser Schicht oder in der zweiten Hälfte sind. Und jetzt für einen süßen Trick - Blick auf das nächste Bit nach dem MSB. Wenn dieses Bit auf 0 gesetzt ist, sind wir in der ersten Hälfte des Bereichs und ansonsten in der zweiten Hälfte des Bereichs. Somit können wir feststellen, in welcher Hälfte des Bereichs wir gerade sind, indem wir uns das nächste Bit der Anzahl ansehen! Dies bedeutet, dass wir bestimmen können, in welchen Teilbaum wir uns begeben, indem wir nur auf das nächste Bit der Zahl schauen.

Sobald wir das getan haben, können wir diesen Vorgang einfach wiederholen. Was machen wir auf der nächsten Ebene? Nun, wenn das nächste Bit eine Null ist, gehen wir nach links, und wenn das nächste Bit eine Eins ist, gehen wir nach rechts. Werfen Sie einen Blick auf das, was bedeutet das für 13:

1101 
    ^^^ 
    ||| 
    ||+--- Go right at the third node. 
    || 
    |+---- Go left at the second node. 
    | 
    +----- Go right at the first node. 

Mit anderen Worten, wir können den Weg von der Wurzel des Baumes zu unserem Knoten in Frage formulieren, indem man sich die Bits der Zahl nach dem MSB !

Funktioniert das immer! Sie wetten! Lassen Sie uns die Nummer 7 versuchen. Dies hat Binärdarstellung 0111. Das MSB ist in der 4-Stelle. Unter Verwendung unseres Algorithmus würden wir das tun:

In unserem ursprünglichen Bild suchen, ist dies der richtige Weg zu nehmen!

Hier einige grobe C/C++ Pseudo-Code für diesen Algorithmus:

Node* NthNode(Node* root, int n) { 
    /* Find the largest power of two no greater than n. */ 
    int bitIndex = 0; 
    while (true) { 
     /* See if the next power of two is greater than n. */ 
     if (1 << (bitIndex + 1) > n) break; 
     bitIndex++; 
    } 

    /* Back off the bit index by one. We're going to use this to find the 
    * path down. 
    */ 
    bitIndex--; 

    /* Read off the directions to take from the bits of n. */ 
    for (; bitIndex >= 0; bitIndex--) { 
     int mask = (1 << bitIndex); 
     if (n & mask) 
      root = root->right; 
     else 
      root = root->left; 
    } 
    return root; 
} 

Ich habe diesen Code nicht getestet! Um Don Knuth zu paraphrasieren, habe ich gerade gezeigt, dass es konzeptionell das Richtige tut. Ich könnte hier einen Fehler von eins nach eins haben.

Wie schnell ist dieser Code? Nun, die erste Schleife läuft, bis sie die erste Potenz von zwei größer als n findet, die O (log n) Zeit benötigt. Der nächste Teil der Schleife zählt rückwärts durch die Bits von n einzeln, wobei O (1) bei jedem Schritt ausgeführt wird. Der Gesamtalgorithmus benötigt somit insgesamt O (log n) Zeit.

Hoffe, das hilft!