查找数组 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 的值等于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的每个分支。这将是O(k)，但很复杂。

要找到 Y <= X 的所有 Y，您不妨扫描整个数组，这将是 O(n)，但开销要少得多。

选择取决于 n/k 比率

Answer 3

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

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

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

从那里你可以得到子树一直向下的结果，直到你到达值>的分支。 x。您最多需要执行 2*k 检查来修剪这些分支，所以在我看来总共是 O(k) 。