Priority queue implementation in C

Question

Is there any reliable and simple priority queue (linked list preferred, not necessary) implementation for C?

More generally, what C standard libraries do you use?

Answer 1

PQLib (the current accepted answer) is incomplete and the functionality doesn't match the documentation as of this posting. E.g., the pq_dequeue documentation says it returns an entry. The implementation returns NULL. There are many "TO DO" comments in the code, such as, "remove node containing highest priority entry from its heap." Essential logic is missing.

To anyone looking for a priority queue: I recommend finding some code that has good, passing unit tests. I don't recommend PQLib unless it's updated and includes tests.

To the owner of PQLib or anyone recommending it: I assumed this code was complete and spent a fair bit of time debugging until I realized it wasn't, which was frustrating. Please don't recommend code you haven't tried or know to be a work in progress.

Answer 2

The source code accompanying Robert Sedgewick's Algorithms in C, Parts 1-4 (Fundamental Algorithms, Data Structures, Sorting, Searching) contains both a heap-based and a list-based implementation. See Chapter 9 - Priority Queues and Heapsort.

Answer 3

I have a priority queue written in C, hosted on google code. MIT license

https://code.google.com/p/pqueue-heap-c/source/browse/trunk/pqueue.cpp

The code has been used in a few projects so it's solid, but I wrote it in '98 so I don't remember how to use it. Don't be misled by the cpp extension. It's straight C.