Priority Queue in R for OPTICS implementation

Question

I need to construct a priority queue in R where i will put the ordered seed objects (or the index of the objects) for the OPTICS clustering algorithm.

• One possibility is to implement it with heap with the array representation, and pass the heap array in each insert and decrease key call, and return the changed array and reassign it in the calling function. In which case, the reassign operation will make the performance very poor and every time one insert or decrease operation is executed the entire array needs to be copied twice, once for calling, and another once for returning and reassigning.

• Another possibility is to code the heap operations inside the function instead of calling it. This will result in code repetition and cumbersome code.

• Is there any pointer like access as we do in C

• Can i declare user defined functions in the S3 or S4 classes in R ? In the the case i think the call to these functions still requires the same reassignment after returning (not like C++/Java classes, operates on the object (am i right?) )

• Is there any builtin way with which i can insert and extract an object in a queue in O(log(n)) time in R?

• Is there any other way with which i can achieve the goal, that is maintain a priority based insertion and removal of the seeds depending on the reachability distance of an object in the OPTICS algorithm, except explicitly sorting after each insertion.

Answer 1

R5 classes define mutable objects, and very similar to Java classes: they should allow you to avoid the copies when the object is modified.

Answer 2

Note that you do not just need a priority queue.

It actually needs to support efficient updates, too. A simple heap is not sufficient, you need to synchronize a hashmap to find objects efficiently for updating their values. Then you need to repair the heap at the changed position.