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 + ")";}
  }
}

Answer 2

只需使用 OneMap<int,int>存储数组的索引和值即可解决。而 One Priority 又Queue<Pair<int,int>> pq存储了对应于priority Queue中优先级的索引和值。

C++ 代码：

#include<bits/stdc++.h>
using namespace std;

// Author : @devangs

int main(){
    int i,j;
    vector<int> v ={1,2,3,4,5,2,5,4};
    int n=v.size();

    unordered_map<int,int> mp;
    for (i=0; i<n; i++)
    {
        mp[i]=v[i];
    }
    
    cout<<"Map With Index and Values Are: "<<endl;
    for (auto it:mp)
        cout<<it.first<<" "<<it.second<<endl;
    
    cout<<endl;
        
    cout<<"Map With Index and PQ Value Are: " <<endl;           
    priority_queue<pair<int,int>> pq; 
    for(auto it = mp.begin(); it != mp.end(); it++)
    {
        pq.push(make_pair(it->second, it->first));
    }
        
    while (!pq.empty()){
        cout<<pq.top().second<<" "<<pq.top().first<<endl;  
        pq.pop();
    }
    return 0;
}