You think that your code is perfect … until you put it up for code review.

I put up my priority queue for review and received lots of really good feedback. Including a memory leak which was embarrassing.

See here:

Priority queue implementation in C based on heap ordered (resizable) array

So I added in most of the suggestions and here it is. I would like to see if I interpreted the suggestions correctly and also see if there is anything else that needs fixing.

I realise of course that to make it really industrial strength, like for example the C library sort functions or the C++ standard library then changes would be required. But hopefully this code is still useful for some uses.

One remaining item that I have not addressed is the array_resize function. Fixing that is not trivial so have left that issue for now. Basically, if realloc fails, what to do.

Here is the code.

priority_queue.h – header:

/* Heap ordered priority queue storing in a resizable array */  #ifndef PRIORITY_QUEUE_ #define PRIORITY_QUEUE_  struct priority_queue; typedef struct priority_queue priority_queue_t;  /* priority_queue_init initialises the priority queue and returns a handle which  must be passed to subsequent priority_queue_xxx functions..  Argument is the comparison function.  This comparison function must return a negative value if the first argument is less than the second, a positive integer value if the  first argument is greater than the second, and zero if the arguments are equal. The function must also not modify the objects passed to it.  The meaning of greater or less can be reversed. */ priority_queue_t* priority_queue_init(int(*compare)(const void* element1, const void* element2)); /* priority_queue_free frees memory used by priority queue. init in constant time */ void priority_queue_free(priority_queue_t* pq); /* returns 1 if the queue is empty, 0 otherwise. constant time */ int priority_queue_empty(const priority_queue_t* pq); /* insert an object into the priority queue. insert in logarithmic time */ void priority_queue_insert(priority_queue_t* pq, void* el); /* pops the 'top' element and removes from the priority queue. pop in logarithmic time */ void* priority_queue_pop(priority_queue_t* pq); /* returns the top element but does not remove from priority queue. top in constant time */ void* priority_queue_top(const priority_queue_t* pq); /* returns number of elements in priority queue. constant time */ int priority_queue_size(const priority_queue_t* pq);  #endif // PRIORITY_QUEUE_ 

priority_queue.c – the implementation:

#include "priority_queue.h"  #include <stdlib.h>  typedef int(*compare)(const void* element1, const void* element2);  struct priority_queue {     int capacity;     int n;     void** array;     compare cmp; };  static const int initial_size = 2; // 16;  static void swap(priority_queue_t* pq, int index1, int index2) {     // shallow copy of pointers only     void* tmp = pq->array[index1];     pq->array[index1] = pq->array[index2];     pq->array[index2] = tmp; }   static void rise(priority_queue_t* pq, int k) {     while (k > 1 && pq->cmp(pq->array[k / 2], pq->array[k]) < 0) {         swap(pq, k, k / 2);         k = k / 2;     } }  static void fall(priority_queue_t* pq, int k) {     while (2 * k <= pq->n) {         int child = 2 * k;         if (child < pq->n && pq->cmp(pq->array[child], pq->array[child + 1]) < 0) {             child++;         }          if (pq->cmp(pq->array[k], pq->array[child]) < 0) {             swap(pq, k, child);         }         k = child;     } }  static void** array_resize(void** array, int newlength) {     /* reallocate array to new size        this is problematic because realloc may fail and return NULL        in which case there is a leak because array is still allocated        but not returned so cannot be free'd */     return realloc(array, newlength * sizeof(void*)); }  priority_queue_t* priority_queue_init(int(*compare)(const void* element1, const void* element2)) {     priority_queue_t* pq = malloc(sizeof(priority_queue_t));     pq->array = NULL;     pq->capacity = 0;     pq->n = 0;     pq->cmp = compare;     return pq; }  void priority_queue_free(priority_queue_t* pq) {     free(pq->array);     free(pq); }  int priority_queue_empty(const priority_queue_t* pq) {     return pq->n == 0; }  void priority_queue_insert(priority_queue_t* pq, void* el) {      if (pq->capacity == 0) {         pq->capacity = initial_size;         pq->array = array_resize(pq->array, pq->capacity + 1);     }     else if (pq->n == pq->capacity) {         pq->capacity *= 2;         // we need to resize the array         pq->array = array_resize(pq->array, pq->capacity + 1);     }      // we always insert at end of array     pq->array[++pq->n] = el;     rise(pq, pq->n); }  void* priority_queue_pop(priority_queue_t* pq) {      // reduce array memory use if appropriate     if (pq->capacity > initial_size && pq->n < pq->capacity / 4) {         pq->capacity /= 2;         pq->array = array_resize(pq->array, pq->capacity + 1);     }      void* el = pq->array[1];     swap(pq, 1, pq->n--);     pq->array[pq->n + 1] = NULL;  // looks tidier when stepping through code - not really necessary     fall(pq, 1);     return el; }  void* priority_queue_top(const priority_queue_t* pq) {     return pq->array[1]; }  int priority_queue_size(const priority_queue_t* pq) {     return pq->n; } 

example driver program:

#include "priority_queue.h"  #include <string.h> #include <stdlib.h> #include <stdio.h>  typedef struct {     int weight;     char* data; } element;   int descending(const void* a, const void* b) {     const element* element1 = a;     const element* element2 = b;     if (element1->weight < element2->weight)         return -1;     if (element1->weight > element2->weight)         return 1;      return 0; }  typedef struct {     int vertex;     int weight; } edge;  int ascending(const void* a, const void* b) {     const edge* edge1 = a;     const edge* edge2 = b;     if (edge2->weight < edge1->weight)         return -1;      if (edge2->weight > edge1->weight)         return 1;      return 0; }  int main() {     priority_queue_t* pq = priority_queue_init(descending);     printf("size of pq now = %d\n", priority_queue_size(pq));      int weights[] = { 14,8,15,16,11,1,12,13,4,10,9,3,5,7,2,6,6,6 };     int size = sizeof(weights) / sizeof(weights[0]);      // insert each one into priority queue     for (int i = 0; i < size; ++i) {         element* el = malloc(sizeof(element));          // generate string         char buffer[20];         sprintf(buffer, "added no: %d", i + 1);         el->data = malloc(strlen(buffer) + 1);         strcpy(el->data, buffer);         el->weight = weights[i];         priority_queue_insert(pq, el);     }     printf("size of pq now = %d\n", priority_queue_size(pq));     element* el = malloc(sizeof(element));     el->weight = 22;     el->data = "hi guys";     priority_queue_insert(pq, el);     printf("size of pq now = %d\n", priority_queue_size(pq));      const element* top = priority_queue_top(pq);     printf("peek of top item: %d %s\n", top->weight, top->data);      while (!priority_queue_empty(pq)) {         element* top = priority_queue_pop(pq);         printf("top is: %d %s\n", top->weight, top->data);         free(top);     }     printf("size of pq now = %d\n", priority_queue_size(pq));     priority_queue_free(pq);      // try using different data/comparator     pq = priority_queue_init(ascending);     edge* e1 = malloc(sizeof(edge));     e1->vertex = 0;     e1->weight = 1;     priority_queue_insert(pq, e1);     edge* e2 = malloc(sizeof(edge));     e2->vertex = 1;     e2->weight = 3;     priority_queue_insert(pq, e2);      edge* e3 = malloc(sizeof(edge));     e3->vertex = 2;     e3->weight = 3;  // same weight     priority_queue_insert(pq, e3);      while (!priority_queue_empty(pq)) {         edge* top = priority_queue_pop(pq);         printf("top is: %d %d\n", top->weight, top->vertex);         free(top);     }     printf("size of pq now = %d\n", priority_queue_size(pq));     priority_queue_free(pq); }