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

Question

I have the code here from Skiena's manual:

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

I don't understand why the count is not being decremented for the right child of the node?

Answer 1

The count does not decrease as when you go towards the right subtree the current node is counted as one of the "k-1" smaller elements and when we move towards the left the current node is not included in the "k" smallest elements.

Answer 2

I agree with @Bugaboo that the code here is a bit misleading, though the accepted answer does provide a reasonable explanation.

I find the solution here is provides a clearer explanation. The counter is updated once the node itself has been compared with x, and then the algorithm moves pseudocode is by @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 is not updated because it is already decremented once for current node and that value is passed into left node's heap_compare method. And the value returned from left node's heap_compare is assigned to count so no need to decrement again. It could be re-written as below.

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