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?

Why do you mean by "what standard libraries?" – WhirlWind Apr 10 '10 at 16:19 — WhirlWind, Apr 10 '10 at 16:19
I like to implement my PQs on top of binomial heaps. – Heath Hunnicutt Jul 05 '10 at 16:38 — Heath Hunnicutt, Jul 05 '10 at 16:38

score 7 · Answer 1 · answered Sep 13 '14 at 21:58

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.

yeah just wasted an hour - should have read a bit more of this thread! — Mark, Dec 28 '16 at 11:05

score 5 · Answer 2 · answered Jun 15 '11 at 18:58

5

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.

answered Jun 15 '11 at 18:58

AShelly

34,686
15
91
152

score 3 · Answer 3 · answered Feb 15 '11 at 22:30

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.

answered Feb 15 '11 at 22:30

justinhj

11,147
11
58
104

What projects have used your code? Thank you for making and sharing this! – Darakian Aug 11 '15 at 22:42
You're welcome @Darakian I used this in some path finding code in a video game quite a long time ago in the late 90's. – justinhj Aug 13 '15 at 04:16
You can't share which game can you? – Darakian Aug 13 '15 at 19:51
This code or at least a similar version of it was used in a Playstation game called Batman and Robin and I also used it in an A* algorithm implementation but it was never used as I later rewrote it in C++ and used STL's built in priority queue. – justinhj Aug 14 '15 at 16:58

score -2 · Accepted Answer · answered Apr 10 '10 at 16:14

-2

Check out PQLib.

I use the standard C standard libraries. ;)

answered Apr 10 '10 at 16:14

WhirlWind

13,974
3
42
42

12

Please, please PLEASE read the LICENSE file in PQLib _very_ carefully. It re-introduces a whole new kind of advertising clause (even worse than the original BSD advertising clause) and is incompatible with the GPL/LGPL (all versions). Basically, you can't link againtst glibc and PQLib and distribute the final product legally. The library is most decidedly _not_ open source, much less free software. – Tim Post Apr 11 '10 at 16:40
1

@Tim I didn't realize... it says BSD, but they must mean special BSD. +1 – WhirlWind Apr 12 '10 at 04:18
1

DO NOT USE PQLIB. It is not complete and does not work. – Mark Dec 28 '16 at 11:07

Priority queue implementation in C

4 Answers4

Linked