6

最小ヒープの配列実装で x より小さいすべてのキーを見つけるアルゴリズムを説明できる人がいますか? 実行時間を少なくとも O(k) にしたいと考えています。ここで、k は報告されたキーの数です。

私はこれでしばらく頭を悩ませてきました。

4

3 に答える 3

4

「少なくとも」の実行時間を取得することはそれほど難しいことではありません、私はあなたが「せいぜい」を意味すると思います。

残念ながら、最小ヒープは最小値以外のものを見つけるのにあまり適していません。

ヒープのツリービューの幅優先探索を実行し、 Xに到達したすべてのブランチを終了できます。これはO（k）になりますが、複雑になります。

Y <= XであるすべてのYを見つけるには、配列全体をスキャンすることもできます。これはO（n）になりますが、オーバーヘッドははるかに少なくなります。

選択は比率n/kに依存します

于 2010-10-20T17:59:34.130 に答える
4

ツリー最小ヒープの単純な再帰アルゴリズムがあります。

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);
}

サブツリーのルートが x 以上の値を持つ場合、最小ヒープの定義により、そのすべての子孫も x 以上の値を持つことになります。アルゴリズムは、通過するアイテムよりも深く探索する必要がないため、O(k) です。

もちろん、これを配列アルゴリズムに変換するのは簡単なことです。

#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);
}
于 2010-10-20T18:18:33.790 に答える
1

配列としての実装は無関係です。トップダウンのツリー検索を実行できます。「従来の」ポインターを使用する代わりに、それぞれの子ノードのインデックスを計算する必要があります。

邪魔にならないように、上から再帰検索を行い、現在のノードが x より大きい各ブランチで再帰を停止します。これにより、一般に、チェックする必要のない多くの値が削除されます。

k 戻り値を使用すると、 O(k) が明らかに最良のケースです。最上位ノードが <= x の場合、すぐに結果を取得し始めます。大きい場合は完了です - 結果は空です。

そこから、値 > x の分岐に到達するまで、サブツリーをずっと下って結果が得られます。これらの枝を剪定するには、最大で 2*k チェックを実行する必要があるため、合計で O(k) のように見えます。

于 2010-10-20T18:18:45.357 に答える