java - 堆优先级队列如何记住其在数组中的索引？

Question

对我来说，实现此队列的最简单方法是什么，以便我可以在每个相应的 MyEntry 对象中保存每个索引(条目在 ArrayList 堆中的位置)，而不使用键或值来执行此操作？

public class HeapPriorityQueue<K,V> {

protected ArrayList<Entry<K,V>> heap;
protected Comparator<K> comp;

protected static class MyEntry<K,V> implements Entry<K,V> {
    protected K key;
    protected V value;
    public MyEntry(K k, V v) {key = k; value = v;}
    public K getKey() {return key;}
    public V getValue() {return value;}
    public String toString() {return "(" + key + "," + value + ")";}
}

Answer 1

您是否正在寻找与此类似的东西？

public class HeapPriorityQueue<K,V> {

  protected ArrayList<Entry<K,V>> heap;
  protected TreeMap<Entry<K,V>, Integer> index;
  protected Comparator<K> comp;

  public synchronized void addEntry(K key, V value) {
    // requires O(log(n))
    Entry<K, V> entry = new Entry<K, V>(key, value);
    int insertionPos = heap.size();
    heap.add(entry);
    index.put(entry, insertionPos);
  }

  public int indexOfEntry(Entry<K,V> entry ) {
    // requires O(log(n))
    return index.get(entry);
  }

  protected static class MyEntry<K,V> implements Entry<K,V> {
    protected K key;
    protected V value;
    public MyEntry(K k, V v) {key = k; value = v;}
    public K getKey() {return key;}
    public V getValue() {return value;}
    public String toString() {return "(" + key + "," + value + ")";}
  }
}