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

Question

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

我一直在为此挠头。

Answer 1

要获得“至少”的运行时间并不难，我假设您的意思是“至多”。

不幸的是，min-heap 并不擅长寻找除最小值之外的任何东西。

您可以对堆的树视图进行广度优先深度优先扫描，并终止到达 X 的每个分支。这将是 O(k)，但很复杂。

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

选择取决于比率 n/k

Answer 2

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

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 3

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

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

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

从那里你得到结果一直到子树，直到你点击值> x的分支。你最多需要做 2*k 检查来修剪这些分支，所以对我来说总共看起来像 O(k)。