在数组min-heap中查找所有小于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);
}

Answer 2

作为数组的实现是无关紧要的，你仍然可以进行自上而下的树搜索。您需要计算相应的子节点索引，而不是使用“经典”指针。

这样，从顶部开始进行递归搜索，并在当前节点大于x的每个分支上停止递归。这通常会删除许多不需要检查的值。

对于k个返回值，O(k)显然是最好的情况。如果您的顶级节点是<= x，您将立即开始获得结果。如果它更大，你就完成了-结果是空的。

从那里你可以得到所有的结果，直到你遇到值大于x的分支。你需要做最多2*k次检查来修剪这些分支，所以对我来说，它看起来总共是O(k)。