Code covered by the BSD License  

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

5.0

5.0 | 4 ratings Rate this file 35 Downloads (last 30 days) File Size: 17.9 KB File ID: #24238
image thumbnail

Priority Queue (MEX/C++)

by

 

22 May 2009 (Updated )

An efficient priority queue implementation in C++

| Watch this File

File Information
Description

Package: priority_queue 0.9
Author: Andrea Tagliasacchi andrea.tagliasacchi@gmail.com
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 (9)
07 Nov 2012 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.

22 Oct 2012 Andrea Tagliasacchi

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

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 ){

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

30 May 2011 Bart  
30 Mar 2011 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)

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:

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

Use an SVN client to check out the source

15 Jul 2010 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;

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?

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.

Updates
20 Feb 2011

Corrected bug on element removal when back-indexing.

Contact us