Priority Queue (MEX/C++)

An efficient priority queue implementation in C++

Description

Package: priority_queue 0.9
Author: Andrea Tagliasacchi [e-mail]
Date: 22 May 2009

%------------------ DESCRIPTION -----------------%
priority_queue provides a minimal implementation of a
priority queue for Matlab. The implementation can be used
either inside MATLAB by means of MEX calls, or directly from a C/C++ program. The image on the website has been created with "pq_demo.m"

Elements in a queue are composed by a simple tuple [index; cost]
The integer index is used to address any array you might design, the floating point cost is used to order the priority queue.

%------------------ FUNCTIONALITIES -----------------%
This implementation offers the following functionalities:
- pq_create: creates a priority queue
- pq_delete: frees the memory allocated
- pq_push: inserts a new element in the queue
- pq_top: queries topmost element in the queue
- pq_pop: retrieves and removes topmost element
- pq_size: queries the queue size

%------------------ FILE STRUCTURE -----------------%
Everyone of the scripts/functions is complete of the following:
*.cpp: the mex implementation of the sources
*.m: the comments that you can browse with the "help" command

%------------------ HOW COMPILE -----------------%
IMPORTANT NOTE: I assume you have a correctly configured MEX environment.
You can compile directly inside MATLAB:
>> mex pq_create.cpp
>> mex pq_delete.cpp
>> % .... etc.
 
%------------------ DEVELOPMENT -----------------%
As mentioned the *.cpp files contain a MEX interface for MATLAB.
- a C++ test/demo program is provided in pq_demo.cpp
- a MATLAB test/demo program is provided in pq_demo.m

%-------------- COMPATIBILITY NOTES --------------%
priority_queue compiles correctly with the following compilers:
- i686-apple-darwin9-g++-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5484)
- Visual studio c++ 6.0 with Service pack 6

---
Feedback is greatly appreciated.

• MATLAB release: MATLAB 7.7 (R2008b)
• Other requirements: MEX compiler correctly setup

[Haw-Shiuan]

In svn version, I found that after line "heap[0] = heap.back();" (line 141 in "MyHeap.h"), we should add " backIdx[ heap[0].second ] = 0;" to preserve the correctness of back index.

[Andrea Tagliasacchi]

The SVN now contains the corrections pointed out by Levi and Jeremy.

[Jeremy Kawahara]

Hi, great code! Thanks for sharing! :)

Two small bugs...

1) The current MinHeap will keep adding elements instead of updating them.

The fix is to remove the extra "useBackIdx" condition in "MyHeap.H" in the MinHeap->void push() function.

So change line 316
======
if( useBackIdx || backIdx[index] == -1 ){

to
if( backIdx[index] == -1 ){
======

2) To get this code to work on a 64-bit machine I had to change the addresses from "long" to "unsigned long long". I did this change pretty much anytime something I saw something was cast to a "long".

Hope that helps!
Thanks! -- Jeremy

[Bart]

 

[Levi]

Nice code, but bug still isn't fixed. It appears the MinHeap code in MyHeap.h was updated, but not the MaxHeap code (which is what is used by the pq_* code)

[Andrea Tagliasacchi]

Tim I updated the backIdx error you pointed out. Up to date source (and OSX binaries) can be found at:

http://latis.cs.sfu.ca/svn/users/ata2/matlibs/myheaps/

Use an SVN client to check out the source

[Tim Holy]

Very nice work. Thanks for sharing this useful code!

I found one small bug: pop does not clear the backIdx, so if you put an index on the heap, pop it off, and then try to put the same index on again with a new (lower) value, you will get an error, even though that index was no longer on the heap.

You can fix this by adding the following lines right after the test to see if the heap is empty:

// Clear the backIdx associated with the element we
// are about to remove
if (useBackIdx)
backIdx[heap[0].second] = -1;

[Andrea Tagliasacchi]

1) The C++ library MyHeap.h contains both implementation for MaxHeap and MinHeaps. All you need is to create interface functions along the lines of those I created for the MinHeaps.

2) This would require to add a function in MyHeaps.h but I don't see why not, it should be a very easy operation to do.

3) Position in the tree? Lowest Level?

[Kit Yates]

This seems like an excellent set of files. A couple of questions.
1) Is it possible to reverse the order of the indexing in order to have the smallest elements at the top (other than the obvious: making all the entries negative when entering them and then converting them back to positive when using them)?
2)Is it possible to access the cost of an element from the priority queue by inputting its index in some way.
3)On a similar note is it possible to access the index and cost of an element by somehow inputting its position in the tree.
i.e. would it be possible to access all the elements on the lowest level.
Thanks, Kit.