Salve! Sto cercando di implementare in Java una min priority queue usando un Heap ma ho un po' di confusione mentale.
A quanto ho capito, una priority queue è una struttura dati che serve a mantenere un insieme di elementi ciascuno con un valore associato (Key).
Per implementare una min priority queue usando un Heap non mi è ben chiaro come dichiarare le varie cose, mi spiego meglio; un heap è un array che può essere visto come un albero binario - no? E tale array per rappresentare un heap deve avere lunghezza dell'array ed elementi dell'heap memorizzati nell'array - giusto?
Mi chiedo quindi, nella mia classe devo per esempio dichiarare un ArrayList (che sarà il mio heap) e due variabili int per salvarmi le due lunghezze? E fatto ciò, nella stessa classe, faccio un costruttore che rappresenta la mia priority queue - usando dentro le due lunghezze dichiarate precedentemente e un ArrayList che rappresenta l'heap chiamando successivamente Heapify per far rispettare l'invariante di MIN priority queue?
cerco di scrivere una bozza di codice per spiegarmi leggermente meglio:
public class PriorityQueue{
private int heapSize = 0;
private int heapCapacity = 0;
private ArrayList<T> heap = null;
public Heap(ArrayList<T> arList) {
heapSize = arList.size();
heapCapacity = arList.size();
heap = new ArrayList<T>(heapCapacity);
// qualcosa per riempire l'heap
// Heapify
}
}
In oltre volevo chiedere, è possibile utilizzare Comparator di Java per facilitare in qualche modo gli ordinamenti?
Spero di essere stato chiaro nelle spiegazioni vi ringrazio in anticipo!