heapsort - 在数组最小堆中查找所有小于 x 的键

Question

有人可以描述一种算法，该算法在最小堆的数组实现中找到所有小于 x 的键。
我希望运行时间至少为 O(k)，其中 k 是报告的键数。

我已经为此挠头一段时间了。

Answer 1

树最小堆有一个简单的递归算法:

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