Find all keys smaller than x in the min-heap array

Question

Can anyone describe an algorithm that will find all keys smaller than x in the implementation of the mini-heap array. I want the runtime to be at least O (k), where k is the number of keys reported.

I'm scratching my head a little.

Answer 1

There is a simple recursive algorithm for a mini-heap tree:

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

If the root of the subtree has a value greater than or equal to x, then, by the definition of a mini-heap, all its descendants will also have values ​​greater than or equal to x. The algorithm should not investigate deeper than objects crossing it; therefore, it is O (k).

Of course, this is a trivial thing translating this into an array algorithm:

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

Answer 2

" ", - , , " ".

, - - , .

, X. O (k), .

Y, Y <= X, , O (n), .

n/k

Answer 3

, . "" node.

, node , x. , , , .

With k return values, O (k) is obviously your best case. If your top node is <= x, then you immediately begin to get the results. If there is more of it, you did it - the result is empty.

From there, you will get the results all the way down the subtree until you click branches with values> x. You should do no more than 2 * k Checks to trim those branches, so that it looks like O (k) as a whole to me.