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?

Neither data structure nor the question is not clear. What is the original problem that this code tries to solve? What is data structure used in the code? Question should be self contained. E.g. pq_young_child!? — Saeed Amiri, Jan 03 '17 at 23:38

score 1 · Accepted Answer · answered Jan 04 '17 at 08:07

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.

answered Jan 04 '17 at 08:07

uSeemSurprised

1,826
2
15
18

Michael · Answer 2 · 2019-09-13T05:26:51.013

1

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

edited Sep 13 '19 at 05:26

answered Sep 13 '19 at 01:10

Michael

11
2

2

Please include the code into your answer and not just refer to it via a link. – Constantin Beer Sep 13 '19 at 01:26
Is `counter` used as the answer to the function? How should it be interpreted? It seems that the possible values are -1, 0, or some number <= k. Thanks – Mehdi Saffar Sep 25 '22 at 19:11

score 1 · Answer 3 · answered Apr 02 '21 at 04:48

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

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

3 Answers3