File Exchange

image thumbnail

ataiya/pq

version 1.3 (12.7 KB) by

An efficient priority queue implementation in C++

6 Downloads

Updated

Priority queue implementation for MATLAB

Comments and Ratings (17)

I have moved the repo to GitHub, I am NOT SUPPORTING this code, but feel free to send in pull requests for fixes you might have.

Shimi

Shimi (view profile)

Nevermind my previous comment, I made a mistake in my sed command.

Shimi

Shimi (view profile)

I'm getting segmentation faults (crashes) on linux (x64) even after changing to unsigned long long. Any ideas?

Hi All,

Posted the modified code, compiled and run on VS2015 VC++2015 compiler on windows 10 x64 platform

to compile in matlab CLI , run mex <filepath/pq_c_file>

https://www.mathworks.com/matlabcentral/fileexchange/60628-priority-queue--mex-c++--for-win-x64

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.

Frazer

Frazer (view profile)

The following code causes MATLAB to crash:

pq = pq_create(10000);
pq_push(pq,1,rand(1));

Similar problem to @borablanca.

borablanca

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

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.

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

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

Bart (view profile)

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)

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

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;

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.

Updates

1.3

ported to github to allow community support

1.1

Corrected bug on element removal when back-indexing.

MATLAB Release
MATLAB 7.7 (R2008b)
Acknowledgements

Inspired: priority-queue--mex-c++--for-win-x64

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

» Watch video

Win prizes and improve your MATLAB skills

Play today