Code covered by the BSD License  

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Priority Queue (MEX/C++)

  • pq_create.mPQ_CREATE construct a priority queue object
  • pq_delete.mPQ_DELETE construct a priority queue object
  • pq_demo.mPQ_DEMO compiles library and illustrate Priority Queue's functionalities
  • pq_pop.mPQ_POP removes the topmost element of the priority queue
  • pq_push.mPQ_PUSH inserts a new element/update a cost in the priority queue
  • pq_size.mPQ_SIZE returns the number of elements in the priority queue
  • pq_top.mPQ_TOP queries for the topmost element of the priority queue (not removing it)
  • View all files
4.4 | 5 ratings Rate this file 16 Downloads (last 30 days) File Size: 17.9 KB File ID: #24238 Version: 1.1
image thumbnail

Priority Queue (MEX/C++)



22 May 2009 (Updated )

An efficient priority queue implementation in C++

| Watch this File

File Information

Package: priority_queue 0.9
Author: Andrea Tagliasacchi
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
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (12)
27 May 2016 Frazer

Frazer (view profile)

Figured out what the issue was. MATLAB x64 requires unsigned long long vs. long. Replacing all instances of long with unsigned long long in all .cpp files fixes the issues.

Comment only
26 May 2016 Frazer

Frazer (view profile)

The following code causes MATLAB to crash:

pq = pq_create(10000);

Similar problem to @borablanca.

30 Jul 2015 borablanca

Created an empty queue and run pq_top on it, it crashed. Anyone has same problem?

Comment only
07 Nov 2012 Haw-Shiuan Chang

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.

22 Oct 2012 Andrea Tagliasacchi

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

Comment only
20 Oct 2012 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 ){

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

Comment only
30 May 2011 Bart

Bart (view profile)

30 Mar 2011 Levi

Levi (view profile)

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)

20 Feb 2011 Andrea Tagliasacchi

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

Use an SVN client to check out the source

Comment only
15 Jul 2010 Tim Holy

Tim Holy (view profile)

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;

Comment only
07 Jul 2009 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?

Comment only
07 Jul 2009 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.

20 Feb 2011 1.1

Corrected bug on element removal when back-indexing.

Contact us