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 Files

__MACOSX/._CHANGES,
__MACOSX/._pq_create.m,
__MACOSX/._pq_delete.m,
__MACOSX/._pq_demo.m,
__MACOSX/._pq_pop.m,
__MACOSX/._pq_push.m,
__MACOSX/._pq_size.m,
__MACOSX/._pq_top.m,
__MACOSX/._README,
CHANGES,
license.txt,
MyHeap.h,
pq_create.cpp,
pq_create.m,
pq_delete.cpp,
pq_delete.m,
pq_demo.cpp,
pq_demo.m,
pq_pop.cpp,
pq_pop.m,
pq_push.cpp,
pq_push.m,
pq_size.cpp,
pq_size.m,
pq_top.cpp,
pq_top.m,
README

[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.

[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?