最小堆中大于或等于 x 的第 K 个最小元素

Question

我这里有 Skiena 手册中的代码：

int heap_compare(priority_queue *q, int i, int count, int x)
{
  if ((count <= 0) || (i > q->n)) return(count);

  if (q->q[i] < x) {
    count = heap_compare(q, pq_young_child(i), count-1, x);
    count = heap_compare(q, pq_young_child(i)+1, count, x);
  }

  return(count);
}

我不明白为什么计数是而不是为节点的右子节点递减？

Answer 1

计数不会减少，因为当您向右子树移动时，当前节点被计为 "k-1" 较小元素之一，而当我们向左移动时，当前节点不包含在 "k" 最小的元素。

Answer 2

我同意@Bugaboo 的观点，这里的代码有点误导，尽管接受的答案确实提供了合理的解释。

我找到了解决方案here 提供了更清晰的解释。一旦节点本身与 x 进行比较，计数器就会更新，然后算法移动伪代码来自@Saeed Amiri：

% determine if the k-th smallest element in a min-heap is less than a given number x
void CheckNode(Node node,int k, int x, ref int counter)
{
    if (node.value > x)
    {
        counter++;
        if (counter >= k)
            return;

        CheckNode(node.Left, k, x, ref counter);
        CheckNode(node.Right,k, x, ref counter);
    }
}

Answer 3

count 未更新，因为它已针对当前节点递减一次，并且该值已传递到左节点的 heap_compare 方法中。并且从左节点的 heap_compare 返回的值分配给 count 所以不需要再次递减。它可以重写如下。

int heap_compare(priority_queue *q, int i, int count, int x)
{
  if ((count <= 0) || (i > q->n)) return(count);

  if (q->q[i] < x) {
    count = count-1;
    count = heap_compare(q, pq_young_child(i), count, x);
    count = heap_compare(q, pq_young_child(i)+1, count, x);
  }

  return(count);
}

最小堆中大于或等于 x 的第 K 个最小元素

Kth smallest element greater than or equal to x in a min heap

algorithm

heap