That heap is an array of pointer, so…

/* instead of this */
   if (q->size >= q->capacity) {
        DEBUG("Priority Queue is full. Cannot add another element .");
        return;
    }
  /* do this … doubles capacity every time */
    if (q->size >= q->capacity) {
        q->capacity *= 2;
        q->data = realloc(q->data, q->capacity * sizeof(*(q->data)));
        NP_CHECK(q->data);
    }

And that's the "realloc" nonsense I was talking about Quix

I suppose. I've never implemented a heap using an array. I've always used node pointers, much like a binary tree.