0

Here is my code:

 public DoubleEndedPriorityQueue(){
     max = new MaxPQ<Element>();
     min = new MinPQ<Element>();
 }
 public void insert(Key item){
     Element thisElement = new Element(item);
     Element thatElement = new Element(item);
     thisElement.element = thatElement;
     thatElement.element = thisElement;
     max.insert(thisElement);
     min.insert(thatElement);
 }
 private class Element{
     Key item;
     Element element;
     private Element(){}
     private Element(Key item){
         this(item,null);
     }
     private Element(Key item,Element element){
         this.item = item;
         this.element = element;
     }
 }

}

i create a data-structure to store a key and the reference pointing to the element which stored the same key in another array(the priority queue is implemented by the array),the problem is:if i find a element in an array ,i want to find the element with the same key in another array in o(1) which means i can know its index in O(1), how can i do it?

lizhengxian
  • 69
  • 12
  • 3
    What makes you think you can? – Andy Turner Jan 16 '17 at 14:11
  • 1
    In C,i can use a pointer to get it,so i want to do the same thing in java – lizhengxian Jan 16 '17 at 14:15
  • _i want to do the same thing in java_ Why would you want to reproduce a feature that was hidden in Java, Java doesn't provide pointers. You have the reference, you can do what you want on the instance with that. – AxelH Jan 16 '17 at 14:17
  • The nearest equivalent of storing the pointer would be to store the index in the other array. – Denys Séguret Jan 16 '17 at 14:19
  • Why would you want to reproduce a feature that was hide in Java, Java doesn't provide pointers. because i think it can be easy to find its position – lizhengxian Jan 16 '17 at 14:20
  • 1
    Unless you directly store the element index in the instance, you can't do this in constant time in Java. – Andy Turner Jan 16 '17 at 14:22
  • Using the index would still be o(n) but that would be the closest thing (but that's gonna be funny to maintain ;) ) – AxelH Jan 16 '17 at 14:25
  • Possible duplicate of [How can I use pointers in Java?](http://stackoverflow.com/questions/1750106/how-can-i-use-pointers-in-java). **Depending on your needs**, you could create a Wrapper class to be your `Cell`, those wrapper reference would be the pointer you need. – AxelH Jan 16 '17 at 14:31
  • Unless you directly store the element index in the instance, you can't do this in constant time in Java.That sounds bad.It's the first step of my solution to implement a method delmax() in a double-ended priority queue, if i can't find it in O(1), how can i implement it in O(logn) – lizhengxian Jan 16 '17 at 14:37
  • Store the array elements in order, according to some `Comparator`, then use [`Arrays.binarySearch`](https://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(T[],%20T,%20java.util.Comparator)). – Andy Turner Jan 16 '17 at 14:41
  • Possible duplicate of How can I use pointers in Java?. Depending on your needs, you could create a Wrapper class to be your Cell, those wrapper reference would be the pointer you need.Sorry it can't solve this specific problem for me. – lizhengxian Jan 16 '17 at 14:42
  • Store the array elements in order, according to some Comparator, then use Arrays.binarySearch. But in the priority implemented by the array,every data may swim and sink,its index isn't instant.i'm afraid that your solution can't do that. – lizhengxian Jan 16 '17 at 14:48
  • Save yourself all the trouble and ditch the idea of trying to keep two priority queues in synch. Implement a [Min-max heap](https://en.wikipedia.org/wiki/Min-max_heap) and be done with it. – Jim Mischel Jan 17 '17 at 15:29

0 Answers0