Return to Answer

• 19.7k
• 2
• 44
• 91

• 19.7k
• 2
• 44
• 91

The other answers make some good points (especially @vnp who caught the two memory leaks — that's a huge deal!). I'll try not to repeat too much.

int compare(const struct element* element1, const struct element* element2) {
 return element1->weight - element2->weight;
}

You should be aware that this comparator can have undefined behavior if element1->weight == -2 and element2->weight == INT_MAX (for example). A better idiom for comparing "things" (not necessarily even integral things) is

int compare(const struct element* a, const struct element* b) {
 return (a->weight < b->weight) ? -1 : (a->weight > b->weight);
}

Your code ends up repeating the keyword struct a lot. You might consider defining

struct priority_queue; // forward-declared
typedef struct priority_queue priority_queue_t;
struct element; // forward-declared
typedef struct element element_t;

so that you could use slimmed-down parameter lists like

void priority_queue_insert(priority_queue_t *pq, element_t *el);

I was as surprised as @chux that priority_queue_top actually popped an element from the queue. I would expect the pop function to be named, well, priority_queue_pop!

Also, it would be nice to document explicitly in the API whether the "pop" operation (currently misnamed "top") pops the smallest element or the biggest element. You could do this in either of two ways:

element_t *priority_queue_min(const priority_queue_t *);
element_t *priority_queue_pop_min(priority_queue_t *);

(and personally I would say _least_element instead of _min for absolute clarity) or

element_t *minheap_top(const minheap_t *);
element_t *minheap_pop(minheap_t *);

In the latter case, we use the convention that a "min-heap" has quick access to the minimum element and a "max-heap" has quick access to the maximum element. The data structure you have here is specifically a "min-heap."

Now, looking at priority_queue_top, I realized that of course I should have known that it modified the heap — because it took a parameter of non-const pointer type! If it wasn't going to modify the heap, it would have taken a pointer-to-const. ...But then I looked and saw this:

int priority_queue_empty(struct priority_queue_t* pq);

Bad! Since empty is definitely a non-modifying operation, we should instead write

int priority_queue_empty(const priority_queue_t *pq);
// ^^^^^

Or, if you know that struct priority_queue is very small (say, 16 bytes or less), then you might consider getting clever and writing

int priority_queue_empty(priority_queue_t pq);

This makes a shallow copy of the heap and passes it in by value; used consistently, this can absolutely enforce that no weird mutations are going on, and even (theoretically) allow the compiler to optimize more. But it's definitely "for advanced users only" and maybe "not a good idea anyway." ;)

The last thing I want to talk about is the "genericity" aspect. Right now you have at least three things that the user might want to customize, and you handle each of them in a different way:

(A) The data that belongs to an "element". Customizable exactly once per program, by defining struct element.

(B) The "less-than" predicate for elements. Customizable per-heap, by passing in a comparator (as a function pointer) to the heap constructor priority_queue_init.

(C) The "swapping" and "popping" behaviors for an element. Not customizable; instead, we hold, swap, and pop pointers to elements.

(D) The source of dynamic memory allocation. Not customizable; we use malloc.

If I were writing this code, I would try to mimic the libc function qsort as much as possible. In particular, I would give the comparator this signature:

typedef int (*priority_queue_comparator_t)(const void *, const void *);

Done right, this could ensure that priority_queue, qsort, and bsearch all play together in a natural way. (You might even look at how the C++ STL defines push_heap and pop_heap to work on arbitrary arrays.)

So we could have an API something like this:

typedef int (*comparator_t)(const void *, const void *);
typedef int (*comparator_r_t)(void *cookie, const void *, const void *);
typedef void (*swapper_t)(void *, void *);
typedef void (*swapper_r_t)(void *cookie, void *, void *);
void push_heap_r(void *base, size_t nel, size_t width,
 void *cookie, comparator_r_t cmp, swapper_r_t swap)
{
 char *a = base;
 int k = nel - 1;
 while (k > 1 && cmp(cookie, a + width * (k / 2), a + width * k) < 0) {
 swap(cookie, a + width * (k / 2), a + width * k);
 k /= 2;
 }
}
typedef struct minheap {
 int capacity;
 int n;
 void **array;
 comparator_t cmp;
} minheap_t;
static int pq_cmp(void *cookie, const void *a, const void *b) {
 minheap_t *pq = cookie;
 return pq->cmp(a, b);
}
static void pq_swap(void *, void *a, void *b) {
 void *tmp = *(void**)a;
 *(void**)a = *(void**)b;
 *(void**)b = tmp;
}
void minheap_insert(minheap_t *pq, void *el)
{
 if (pq->n == pq->capacity) {
 pq->capacity *= 2;
 // we need to resize the array
 pq->array = array_resize(pq->array, pq->capacity);
 }
 // we always insert at end of array
 pq->array[++pq->n] = el;
 push_heap_r(pq->array, pq->n, sizeof(void*), pq, pq_cmp, pq_swap);
}

The "cookie" parameter can be used to pass data from the caller, through the generic algorithm push_heap_r, into the comparison function. In this instance we're using the cookie to pass the user's original function pointer pq->cmp through to be used by pq_cmp.

But the user could just as well use push_heap_r on their data array directly, with no indirection through void*s.

static int generic_memcmp(void *cookie, const void *a, const void *b) {
 return memcmp(a, b, *(size_t*)cookie);
}
static void generic_swap(void *cookie, void *a, void *b) {
 size_t n = *(size_t*)cookie;
 char buffer[n]; // VLA alert!
 memcpy(buffer, a, n);
 memcpy(a, b, n);
 memcpy(b, buffer, n);
}
void test() {
 struct foo arr[100] = ...;
 size_t sz = sizeof (struct foo);
 // Build a heap.
 for (int i=1; i <= 100; ++i) {
 push_heap_r(arr, i, sz, &sz, generic_memcmp, generic_swap);
 }
 // Now all 100 `foo`s in the array have been arranged heapwise,
 // according to the comparator defined by memcmp.
}

Now, this is probably getting a little crazy and going off in directions where you might not need so much genericity. But this is the direction I'd think about going. It's pretty unrecognizable compared to our starting point of "require the user to define struct element," and yet the usage of it has maybe even gotten simpler. No more malloc, no more element, no more arrays of pointers... just the rawest possible thing that could be called a "heap." And then we built the malloc'ing minheap_t on top of that.

Anyway, it's food for thought, even if YAGNI in practice. :)