Finden Sie alle Schlüssel, die kleiner als x in einem array min-heap

Kann jemand beschreiben einen Algorithmus, der findet alle Schlüssel, die kleiner als x in einem array Implementierung eines min-Heaps.
Ich will, dass die Laufzeit mindestens O(k), wo k ist die Anzahl der Schlüssel gemeldet.

Ich habe meinen Kopf kratzen für eine Weile jetzt mit diesem.

  • Vielen Dank für die Hilfe!!! Ich weiß es zu schätzen.
InformationsquelleAutor fmunshi | 2010-10-20
  1. 4

    Gibt es einen einfachen rekursiven Algorithmus für ein Baum ein min-heap:

    void smaller_than(Node *node, int x)
{
    if (node->value >= x)
    {
        /* Skip this node and its descendants, as they are all >= x . */
        return;
    }

    printf("%d\n", node->value);

    if (node->left != NULL)
        smaller_than(node->left, x);
    if (node->right != NULL)
        smaller_than(node->right, x);
}

    Wenn ein Teilbaum-Wurzel hat einen Wert, der größer als oder gleich x, dann ist, per definition eines min-Heaps, alle seine Nachkommen haben auch Werte, die größer als oder gleich x ist. Der Algorithmus muss nicht tiefer als die Elemente, die seine durchqueren, es ist also O(k).

    Natürlich, es ist eine triviale Angelegenheit zu übersetzen und diese zu einem array Algorithmus:

    #define ROOT       0
#define LEFT(pos)  ((pos)*2 + 1)
#define RIGHT(pos) ((pos)*2 + 2)

void smaller_than(int x, int pos, int heap[], int count)
{
    /* Make sure item exists */
    if (pos >= count)
        return;

    if (heap[pos] >= x)
    {
        /* Skip this node and its descendants, as they are all >= x . */
        return;
    }

    printf("%d\n", heap[pos]);

    smaller_than(x, LEFT(pos), heap, count);
    smaller_than(x, RIGHT(pos), heap, count);
}
    • ist die pos-variable notwendig? und ist zählen die Länge des Arrays?
    • pos wird verwendet, um beziehen sich auf den aktuellen "Knoten" und ist auch erforderlich, in den Berechnungen der linken und rechten "Knoten". Und ja, count ist die Länge des Arrays. Natürlich muss das array in heap-form für diesen Algorithmus zu arbeiten.
    InformationsquelleAutor Joey Adams
  2. 4

    Bekommen eine Laufzeit von "mindestens" etwas ist nicht so schwierig, ich nehme an, du meinst 'am meisten'.

    Leider ein min-heap ist nicht sehr gut zu finden, alles andere als der kleinste Wert.

    Können Sie eine Breite-zuerst depth-first-scan der Baum-Ansicht von Ihrem Haufen, und beenden Sie jeden Zweig, wo Sie erreicht haben X. Dies wird O(k), aber kompliziert.

    Finden alle Y, wo Y <= X könnte man auch Scannen das gesamte array, dieses wird O(n), aber mit viel weniger Aufwand.

    Die Wahl hängt von dem Verhältnis n/k

    InformationsquelleAutor Henk Holterman
  3. 1

    Die Implementierung als array irrelevant ist, können Sie immer noch eine top-down-Baum-Suche. Nur anstelle des "klassischen" Zeiger, Sie berechnen die entsprechenden Kind-Knoten-Indizes.

    Mit, dass aus der Art und Weise eine rekursive Suche aus dem top-und stop-recursing auf jedem Zweig, bei dem der aktuelle Knoten größer als x ist. Das wird im Allgemeinen prune entfernt eine Menge von Werten, die Sie nicht brauchen, um zu überprüfen.

    Mit k Rückgabewerte O(k) ist offensichtlich Ihre besten Fall. Wenn Ihr top-Knoten <= x, fängst du an, Ergebnisse sofort. Wenn seiner größer ist, sind Sie fertig - das Ergebnis ist leer.

    Von dort erhalten Sie Ergebnisse, die alle der Weg nach unten ist der Teilbaum, bis Sie schlagen die Zweige mit den Werten > x. Sie tun müssen, ist höchstens 2*k Prüfungen prune diese Zweige, so dass es aussieht wie O(k) insgesamt zu mir.

    InformationsquelleAutor TToni
Schreibe einen Kommentar