Return two values with pop function from priority queue

Question

I have priority queue which returns with pop function just int y, but I need return int x and int y. So I found, that I can use struct (struct point) to return two values from function, but I can't figure, how it implement (rewrite int out to struct and use it in main).

Structs:

typedef struct { int x; int y; int pri; } q_elem_t;
typedef struct { q_elem_t *buf; int n, alloc; } pri_queue_t, *pri_queue;
struct point{int PointX; int PointY;};

Pop function:

int priq_pop(pri_queue q, int *pri)
{
  int out;
  if (q->n == 1) return 0;

  q_elem_t *b = q->buf;

  out = b[1].y;
  if (pri) *pri = b[1].pri;

  /* pull last item to top, then down heap. */
  --q->n;

  int n = 1, m;
  while ((m = n * 2) < q->n) {
    if (m + 1 < q->n && b[m].pri > b[m + 1].pri) m++;

    if (b[q->n].pri <= b[m].pri) break;
    b[n] = b[m];
    n = m;
  }

  b[n] = b[q->n];
  if (q->n < q->alloc / 2 && q->n >= 16)
    q->buf = realloc(q->buf, (q->alloc /= 2) * sizeof(b[0]));

  return out;
}

Use in main():

  /* pop them and print one by one */
  int c; 
  while ((c = priq_pop(q, &p)))
  printf("%d: %d\n", p, c);

I'm starting with C, so I will be gratefull for any help.

usually pop only pops one variable, and you call pop twice. var1 = x.pop(); var2=x.pop(); — ddoor, Jan 03 '14 at 12:00
@FaddishWorm if I understand correctly OP tries to store pairs of values in the heap instead of a simple int. — Ivaylo Strandjev, Jan 03 '14 at 12:01

score 1 · Answer 1 · answered Jan 03 '14 at 12:34

You can declare your structures like so:

typedef struct queue_element_struct { // It's good practice to name your structs
   int x,y;
   int pri;
} queue_element_t;

typedef struct priority_queue_struct { 
   queue_element_t *buf; 
   int n, alloc; 
} pri_queue_t, *pri_queue; // Don't know what `*pri_queue` is for

Then change your function to return a pointer to a queue_element_t structure

queue_element_t * priq_pop(pri_queue q, int *pri)

Change

int out;
if (q->n == 1) return 0;
q_elem_t *b = q->buf;

out = b[1].y;

To

// Create new pointer to queue_element_t structure
// that will be returned by this function
queue_element_t *out;
out = (queue_element_t *) malloc(sizeof(queue_element_t));
if (! out) {
  // Could not allocate
}
if (q->n == 1) return 0;

// Set data from queue
out->x = q->buf[1].x;
out->y = q->buf[1].y;

I don't know exactly what your function does, but that is how you return a structure in C.

You said you're just starting with C, so I recommend:

“Code Complete” book by Steve McConnell. It is very useful to comment your code (no matter how small)
properly name your variables: http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Variable_Names
learn about pointers. All you can read about them, read it.

score 1 · Answer 2 · answered Jan 03 '14 at 12:36

You could make your queue data of type struct point

Structs:

typedef struct point{int PointX; int PointY;} q_data; 
typedef struct { q_data d; int pri; } q_elem_t;
typedef struct { q_elem_t *buf; int n, alloc; } pri_queue_t, *pri_queue;

Pop function:

q_data priq_pop(pri_queue q, int *pri)
{
  q_data out = {0,0};
  if (q->n == 1) return out;

  q_elem_t *b = q->buf;

  out = b[1].d;
  if (pri) *pri = b[1].pri;

  /* pull last item to top, then down heap. */
  --q->n;

  int n = 1, m;
  while ((m = n * 2) < q->n) {
    if (m + 1 < q->n && b[m].pri > b[m + 1].pri) m++;

    if (b[q->n].pri <= b[m].pri) break;
    b[n] = b[m];
    n = m;
  }

  b[n] = b[q->n];
  if (q->n < q->alloc / 2 && q->n >= 16)
    q->buf = realloc(q->buf, (q->alloc /= 2) * sizeof(b[0]));

  return out;
}

Use in main():

  /* pop them and print one by one */
  q_data c; 
  while ((c = priq_pop(q, &p)))
  printf("%d: %d, %d\n", p, c.PointX, x.PointY);

Something like this should do the trick. I didn't test it though, so there might be errors. good luck!

score 0 · Answer 3 · edited May 23 '17 at 10:32

In C++ you would use a vector or something similar to store an array of Unfortunately you can't fall back on this.

Why not use an array though, you could have your queue be an array of q_elem_t?

q_elem_t *my_array = q_elem_t array[100]; //pseudo code

For more about making an array of structs see here: How do you make an array of structs in C?

The only thing with an array is that you need to either malloc an arbitrary size (i.e. array[100]) or you need to dynamically control the memory of the array. If you are starting out it might just be best to declare an array of size 100.

To me it looks like the confusion is in the lack of datastructure. Array is a good starting point but if you want to learn more check out linked lists and things like that.

Return two values with pop function from priority queue

3 Answers3