How to properly prioritize priority queue heap in ascending order in C?

Question

My program for school works almost as expected, my priority queue is able to have values inserted and removed properly, and things are stored as expected. However my output looks strange as the values are not matching in the expected column, and the data is being displayed out of order. I feel that the issue may be in my pq_insert function as I am not assigning priority correctly.

The expected output should be like this (the numbers are random of course)

1 /    1 /    1 (   1)
1 /    1 /    1 (   1)
2 /    2 /    2 (   2)
14 /   14 /   14 (  14)
14 /   14 /   14 (  14)
25 /   25 /   25 (  25)
26 /   26 /   26 (  26)
26 /   26 /   26 (  26)

first/removed/priority (expected

However I get something like this:

2/2/2 (1)
1/1/1 (4)
4/4/4 (3)
3/3/3 (2)

I tried rewriting my pq_insert several different ways, I feel like I need something that properly percolates things up and reorder but I am not too sure if I can get anything working. Here is my latest draft

   

#include <stdlib.h>

#include "pq.h"
#include "dynarray.h"

/*
 * This is the structure that represents a priority queue.  You must define
 * this struct to contain the data needed to implement a priority queue.
 */
struct pq {
    struct dynarray* array;
};
struct pq_node 
{
    int priority;
    void* value;
};


/*
 * This function should allocate and initialize an empty priority queue and
 * return a pointer to it.
 */
struct pq* pq_create() {
    /*
     * FIXME: 
     */
    struct pq* new_pq = malloc(sizeof(struct pq));

    //Memory
    if (new_pq == NULL) {
        exit(EXIT_FAILURE);
    }

    new_pq->array = dynarray_create();

    return new_pq;
}


/*
 * This function should free the memory allocated to a given priority queue.
 * Note that this function SHOULD NOT free the individual elements stored in
 * the priority queue.  That is the responsibility of the caller.
 *
 * Params:
 *   pq - the priority queue to be destroyed.  May not be NULL.
 */
void pq_free(struct pq* pq) {
    /*
     * FIXME: 
     */
    dynarray_free(pq->array);
    free(pq);
    return;
}


/*
 * This function should return 1 if the specified priority queue is empty and
 * 0 otherwise.
 *
 * Params:
 *   pq - the priority queue whose emptiness is to be checked.  May not be
 *     NULL.
 *
 * Return:
 *   Should return 1 if pq is empty and 0 otherwise.
 */
int pq_isempty(struct pq* pq) {
    /*
     * FIXME: 
     */
    return dynarray_size(pq->array) == 0;
}


/*
 * This function should insert a given element into a priority queue with a
 * specified priority value.  Note that in this implementation, LOWER priority
 * values are assigned to elements with HIGHER priority.  In other words, the
 * element in the priority queue with the LOWEST priority value should be the
 * FIRST one returned.
 *
 * Params:
 *   pq - the priority queue into which to insert an element.  May not be
 *     NULL.
 *   value - the value to be inserted into pq.
 *   priority - the priority value to be assigned to the newly-inserted
 *     element.  Note that in this implementation, LOWER priority values
 *     should correspond to elements with HIGHER priority.  In other words,
 *     the element in the priority queue with the LOWEST priority value should
 *     be the FIRST one returned.
 */
void pq_insert(struct pq* pq, void* value, int priority) {
    /*
     * FIXME:
     */
    int index = 0;

    //Memory
    struct pq_node* new_node = malloc(sizeof(struct pq_node));
    if (new_node == NULL) {
        
        exit(EXIT_FAILURE);
    }

    new_node->value = value;
    new_node->priority = priority;
    while (index < dynarray_size(pq->array) && ((struct pq_node*)dynarray_get(pq->array, index))->priority <= priority) {
        index++;
    }
    dynarray_insert(pq->array, new_node, index);
}


/*
 * This function should return the value of the first item in a priority
 * queue, i.e. the item with LOWEST priority value.
 *
 * Params:
 *   pq - the priority queue from which to fetch a value.  May not be NULL or
 *     empty.
 *
 * Return:
 *   Should return the value of the first item in pq, i.e. the item with
 *   LOWEST priority value.
 */
void* pq_first(struct pq* pq) {
    /*
     * FIXME: 
     */

    if (pq_isempty(pq)) 
    {
        return NULL;
    }
    return ((struct pq_node*)dynarray_get(pq->array, 0))->value;
}




/*
 * This function should return the priority value of the first item in a
 * priority queue, i.e. the item with LOWEST priority value.
 *
 * Params:
 *   pq - the priority queue from which to fetch a priority value.  May not be
 *     NULL or empty.
 *
 * Return:
 *   Should return the priority value of the first item in pq, i.e. the item
 *   with LOWEST priority value.
 */
int pq_first_priority(struct pq* pq) {
    /*
     * FIXME: 
     */
    if (pq_isempty(pq)) 
    {   
        return 0;
    }

    return ((struct pq_node*)dynarray_get(pq->array, 0))->priority;

}


/*
 * This function should return the value of the first item in a priority
 * queue, i.e. the item with LOWEST priority value, and then remove that item
 * from the queue.
 *
 * Params:
 *   pq - the priority queue from which to remove a value.  May not be NULL or
 *     empty.
 *
 * Return:
 *   Should return the value of the first item in pq, i.e. the item with
 *   LOWEST priority value.
 */
void* pq_remove_first(struct pq* pq) {
    /*
     * FIXME: 
     */
    if (pq_isempty(pq)) 
    {
        return NULL;
    }

    struct pq_node* first_node = dynarray_get(pq->array, 0);
    dynarray_remove(pq->array, 0);
    void* value = first_node->value;
    free(first_node); 
    return value;
}

/*
 * This is a small program to test your priority queue implementation.
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "pq.h"

/*
 * This is a comparison function to be used with qsort() to sort an array of
 * integers into ascending order.
 */
int ascending_int_cmp(const void * a, const void * b) {
  return ( *(int*)a - *(int*)b );
}


int main(int argc, char** argv) {
  struct pq* pq;
  int* first, * removed;
  int i, k, p;
  const int n = 16, m = 16;
  int vals[16 + 16], sorted[16 + 16];

  /*
   * Seed the random number generator with a constant value, so it produces the
   * same sequence of pseudo-random values every time this program is run.
   */
  srand(0);

  /*
   * Create priority queue and insert pointers to pseudo-random integer values
   * into it with the same priority as the value.
   */
  pq = pq_create();
  printf("== Inserting some values into PQ\n");
  for (int i = 0; i < n; i++) {
    vals[i] = rand() % 64;
    pq_insert(pq, &vals[i], vals[i]);
  }

  /*
   * Make a copy of the random value array and sort it by ascending value.  We
   * make a copy here so we can maintain the original array in the same order,
   * thereby ensuring that pointer values stored in the priority queue always
   * point to the same integer values.
   */
  memcpy(sorted, vals, n * sizeof(int));
  qsort(sorted, n, sizeof(int), ascending_int_cmp);

  /*
   * Examine and remove half of the values currently in the PQ.
   */
  k = 0;
  printf("\n== Removing some from PQ: first / removed / priority (expected)\n");
  while (k < n / 2) {
    p = pq_first_priority(pq);
    first = pq_first(pq);
    removed = pq_remove_first(pq);
    if (first && removed) {
      printf("  - %4d / %4d / %4d (%4d)\n", *first, *removed, p, sorted[k]);
    } else {
      printf("  - (NULL) / (NULL) / %4d (%4d)\n", p, sorted[k]);
    }
    k++;
  }

  /*
   * Add a second set of pseudo-random integer values to the end of the array,
   * and add pointers to those values into the priority queue with the same
   * priority as the value.
   */
  printf("\n== Inserting more values into PQ\n");
  for (i = n; i < n + m; i++) {
    vals[i] = rand() % 64;
    pq_insert(pq, &vals[i], vals[i]);
  }

  /*
   * Copy the second array of random values to the end of the sorted array and
   * re-sort all of the the sorted array except the k values that were already
   * examined above (since they were already removed from the PQ, and we won't
   * see them again).  Again, we make a copy here so we can maintain the
   * original array in the same order, thereby ensuring that pointer values
   * stored in the priority queue always point to the same integer values.
   */
  memcpy(sorted + n, vals + n, m * sizeof(int));
  qsort(sorted + k, n - k + m, sizeof(int), ascending_int_cmp);

  printf("\n== Removing remaining from PQ: first / removed / priority (expected)\n");
  while (k < n + m && !pq_isempty(pq)) {
    p = pq_first_priority(pq);
    first = pq_first(pq);
    removed = pq_remove_first(pq);
    if (first && removed) {
      printf("  - %4d / %4d / %4d (%4d)\n", *first, *removed, p, sorted[k]);
    } else {
      printf("  - (NULL) / (NULL) / %4d (%4d)\n", p, sorted[k]);
    }
    k++;
  }

  printf("\n== Is PQ empty (expect 1)? %d\n", pq_isempty(pq));
  printf("== Did we see all values we expected (expect 1)? %d\n", k == m + n);

  pq_free(pq);
  return 0;

}

Answer 1

Because the boilerplate code wasn't posted (e.g. dynarray.h, dynarray.c, pq.h), I cloned the git repo mentioned in my top comments: https://github.com/gallek/CS261-assign_4/tree/master

I'm pretty sure this is a/the correct code because the [boilerplate] comments on the files that you did provide were virtually identical.

That tree had a completed/correct pq.c.

---

When I replaced the pq.c with your version and tried to compile I got:

pq.c: In function ‘pq_insert’:
pq.c:119:29: warning: passing argument 2 of ‘dynarray_insert’ makes integer from pointer without a cast [-Wint-conversion]
  dynarray_insert(pq->array, new_node, index);
                             ^~~~~~~~
In file included from pq.c:5:
dynarray.h:45:47: note: expected ‘int’ but argument is of type ‘struct pq_node *’
 void dynarray_insert(struct dynarray* da, int idx, void* val);
                                           ~~~~^~~
pq.c:119:39: warning: passing argument 3 of ‘dynarray_insert’ makes pointer from integer without a cast [-Wint-conversion]
  dynarray_insert(pq->array, new_node, index);
                                       ^~~~~
In file included from pq.c:5:
dynarray.h:45:58: note: expected ‘void *’ but argument is of type ‘int’
 void dynarray_insert(struct dynarray* da, int idx, void* val);
                                                    ~~~~~~^~~
gcc --std=c99 -g test.c pq.o dynarray.o -o test
gcc --std=c99 -g unittest.c pq.o dynarray.o -o unittest

---

The issue is that, in pq_insert, you do:

dynarray_insert(pq->array, new_node, index);

AFAICT, the last two arguments are reversed. The code builds but with a warning.

If we try to run the code, we get UB (undefined behavior). On my system, I got an assert failure. On your system, you got incorrect results.

When we reverse the arguments, the correct call is:

dynarray_insert(pq->array, index, new_node);

This now compiles cleanly.

---

Here is the output of the test programs. They are identical to the output of the pq.c from the git repo.

Here is ./test:

== Inserting some into PQ

== Removing some from PQ: first / removed / priority (expected)
  -    6 /    6 /    6 (   6)
  -    6 /    6 /    6 (   6)
  -   10 /   10 /   10 (  10)
  -   13 /   13 /   13 (  13)
  -   17 /   17 /   17 (  17)
  -   35 /   35 /   35 (  35)
  -   39 /   39 /   39 (  39)
  -   41 /   41 /   41 (  41)

== Inserting more into PQ

== Removing remaining from PQ: first / removed / priority (expected)
  -    2 /    2 /    2 (   2)
  -    9 /    9 /    9 (   9)
  -   13 /   13 /   13 (  13)
  -   20 /   20 /   20 (  20)
  -   26 /   26 /   26 (  26)
  -   26 /   26 /   26 (  26)
  -   27 /   27 /   27 (  27)
  -   31 /   31 /   31 (  31)
  -   35 /   35 /   35 (  35)
  -   39 /   39 /   39 (  39)
  -   40 /   40 /   40 (  40)
  -   41 /   41 /   41 (  41)
  -   43 /   43 /   43 (  43)
  -   44 /   44 /   44 (  44)
  -   46 /   46 /   46 (  46)
  -   50 /   50 /   50 (  50)
  -   51 /   51 /   51 (  51)
  -   51 /   51 /   51 (  51)
  -   54 /   54 /   54 (  54)
  -   56 /   56 /   56 (  56)
  -   58 /   58 /   58 (  58)
  -   59 /   59 /   59 (  59)
  -   60 /   60 /   60 (  60)
  -   63 /   63 /   63 (  63)

== Is PQ empty (expect 1)? 1

Here is the output of ./unittest:

Test pq_create...                               [   OK   ]
Test pq_insert_single...                        [   OK   ]
Test pq_insert_multiple...                      [   OK   ]
SUCCESS: All unit tests have passed.