CODEWITHSUNDEEP
c
Yuval Adam
Yuval Adam

Reputation: 165202

Priority queue implementation in C

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?

Upvotes: 6

Views: 12688

Answers (4)

dsh
dsh

Reputation: 71

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.

Upvotes: 7

AShelly
AShelly

Reputation: 35520

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.

Upvotes: 5

justinhj
justinhj

Reputation: 11306

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.

Upvotes: 3

WhirlWind
WhirlWind

Reputation: 14112

Check out PQLib.

I use the standard C standard libraries. ;)

Upvotes: -2

Related Questions