Heap-Sort Bekommen Muttergesellschaft

Bekommen ein parent eines Knoten in einem heap-sort-array, die Berechnung würde (index - 1) /2.

Jedoch davon ausgehen, dass jedes Knotens dauert bis 4 Räume, in den array. Zugriff auf einen Datensatz/Knoten, ich muss auf die erste position der vier, die-Rekord. Hier also ein Beispiel:

Wenn ein Elternteil beginnt an der position 4, das linke Kind beginnt an der position 12 und das Rechte Kind startet auf position 16. Die Gleichung für das linke Kind wäre 2*position + 4 und die Gleichung, um die richtige Kind wäre 2*position + 8.

Was wäre die Gleichung zu bekommen, die Eltern aber? Ich brauche eine Gleichung zu erhalten die Eltern entweder das linke Kind oder das Rechte Kind, auf die gleiche Weise index-1/2 tut. Wäre das möglich? Wenn ich zwei getrennte Gleichungen, das würde nicht funktionieren, da ich nicht wirklich weiß, ob ein Datensatz ist eine linke oder eine Rechte Kind.

Danke,

  • Erm, warum sollte ein Knoten nehmen Sie 4 Räume? Es dauert eine.
  • Denn das ist, wie ich es will.. ich bin dabei eine modifizierte version von heap-sort, dass Sie nicht haben, um sorgen über die details.
  • Aber du bist um Hilfe zu bitten mit den details 😉
  • Nicht wirklich.. Seine Art eine mathematische/Algorithmus Frage, unabhängig davon, wie die details der Arbeit.
InformationsquelleAutor darksky | 2011-10-31
  1. 0

    Lassen Sie den ersten index (oder, in diesem Fall die ersten vier Indizes), leer; dies vereinfacht die Berechnungen. Also der root sollte bei 4-7, die Wurzel die Kinder von 8-11 und 12-15, und so weiter. Angesichts dieser, ein Knoten parent in index /8 * 4. Wenn Sie die Wurzel werden in 0-3, können Sie (index + 4) /8 * 4 - 4.

    (Allerdings sollten Sie das einwickeln der vier Elemente in einer Klasse, so dass es leichter sein wird, mit Ihnen zu arbeiten und Sie behandeln können ein einzelnes array-element zu einem Zeitpunkt.)

    • Und das funktioniert nicht. Für das linke Kind 12, 12/8*4 = 6 und für das Recht, Kind 16, 16/8*4 = 8. Die Antwort sollte sein 4 für beide.
    • Ich kann auch gar nicht wickeln die vier Elemente zusammen, da bin ich den Umgang mit den bytes einer Datei.
    • In der integer-division, 12/8 = 1. Also 12/8-Takt * 4 = 4. Nicht die algebra, zu tun, was der computer tut.
    • Wie ich sagte: wenn du die Wurzel bei 0-3, müssen Sie (index + 4) / 8 * 4 - 4, und denken Sie daran, dass ein integer geteilt durch integer ist ein integer in Java. So (12 + 4) / 8 * 4 - 4 == 2 * 4 - 4 == 4, und (16 + 4) / 8 * 4 - 4 == 2 * 4 - 4 == 4.
    InformationsquelleAutor Aasmund Eldhuset
  2. 1

    Blick auf die folgenden C# Min-heap.

        public int GetParent(int i, out int index)
    {
        double element = i;
        index = (int)Math.Floor((element - 1)  / 2);

        if(index < 0)
        {
            return 0;
        }

        return _collection[index];
    }

    Dies funktioniert für regelmäßige heap impl.

    können Sie sehen, der rest des MinHeap Umsetzung hier.

    In der Regel, heap-Struktur ist gesichert mit einem array und interessant, heap beginnen möchte aus dem ArrayEins, um die Berechnung der parent und childs einfach.

    wenn Sie möchten, ändern Sie das Kind, Elternteil, wie Sie erwähnt in Ihrem problem, sollten Sie überlegen, wickeln Sie Ihre 4-Knoten in einem Knoten, aber halten, wie heap funktioniert, wie es ist

    • Ich bin unfähig, wickeln Sie Sie in eine Klasse, da bin ich den Umgang mit den bytes.
    • ArrayList<Btye[]> ...
    • das für kleine Dinge, aber denken Sie über eine riesige in-memory-ARGB-bitmap mit 4 bytes pro pixel, das ist es nicht Wert das erstellen eines Objekts/4-langen-array für jedes pixel.
    InformationsquelleAutor DarthVader
Schreibe einen Kommentar