Sei a conoscenza di una libreria popolare (Apache, Google, ecc.) Che ha un'implementazione Java affidabile per un heap min-max, ovvero un heap che consente di sbirciare il suo valore minimo e massimo in O(1) e di rimuovere un elemento in O(log n)?Implementazione Java per Min-Max Heap?
Da Guava: MinMaxPriorityQueue.
La classe java.util.TreeSet.
Ho bisogno di supporto per valori duplicati ... L'impostazione è "un po '" problematica sotto questo aspetto. –
-1 TreeSet implementa la maggior parte delle operazioni in O (log n) - il requisito era quello di dare una sbirciatina al minimo e al massimo in O (1). – Avi
TreeSet inoltre non ha un'operazione di diminuzioneKey o increaseKey, che è una delle operazioni definitive di un heap. Vedi http://en.wikipedia.org/wiki/Heap_(data_structure) – NamshubWriter
Che ne dici di com.aliasi.util.MinMaxHeap? Questo fa parte di LingPipe; sfortunatamente, il licensing potrebbe essere un problema.
Vedere this related paper.
Non implementa dropsKey o increaseKey, comunque.
Invece di un heap max-min, è possibile utilizzare due istanze di uno java.util.PriorityQueue contenenti gli stessi elementi? La prima istanza sarebbe passata a un comparatore che mette il massimo alla testa, e la seconda istanza userebbe un comparatore che mette il minimo alla testa.
Lo svantaggio è che aggiungere, eliminare, ecc. Dovrebbe essere eseguito su entrambe le strutture, ma dovrebbe soddisfare le vostre esigenze.
+1.Questa è una buona risposta dati i requisiti dichiarati per vedere la radice in O (1) e rimuoverla in O (log.n). Si noti, tuttavia, che PriorityQueue non implementa tutte le operazioni heap (ad esempio reducedKey, increaseKey). – dty
Si noti che l'argomento no remove() ', che rimuove dal capo della coda, è' O (log (n)) ', mentre' remove (Object o) ', è' O (n) '. Riferimento: http://docs.oracle.com/javase/8/docs/api/java/util/PriorityQueue.html – erwaman
Downvoted perché la rimozione non sarà più O (log n). La rimozione del minimo da una delle code è O (log n), ma la rimozione dell'elemento identico, che sarà alla fine dell'altra coda, è O (n). –
private void heapifyUp(int current) {
int parent = (current - 1)/2;
if (current < 0)return;
while (current > 0 && arr[current] > arr[parent]) {
int temp = arr[parent];
arr[parent] = arr[current];
arr[current] = temp;
current = parent;
parent = (current - 1)/2;
} return;
}
Java ha buoni strumenti per implementare gli heap min e max. Il mio suggerimento sta usando la struttura dei dati delle code di priorità per implementare questi heap. Per l'attuazione del cumulo massimo con coda di priorità provare questo:
import java.util.PriorityQueue;
public class MaxHeapWithPriorityQueue {
public static void main(String args[]) {
// create priority queue
PriorityQueue<Integer> prq = new PriorityQueue<>((x,y) -> y-x);
// insert values in the queue
prq.add(6);
prq.add(9);
prq.add(5);
prq.add(64);
prq.add(6);
//print values
while (!prq.isEmpty()) {
System.out.print(prq.poll()+" ");
}
}
}
per l'attuazione del min heap con coda di priorità, provate questo:
import java.util.PriorityQueue;
public class MinHeapWithPriorityQueue {
public static void main(String args[]) {
// create priority queue
PriorityQueue<Integer> prq = new PriorityQueue <>();
// insert values in the queue
prq.add(6);
prq.add(9);
prq.add(5);
prq.add(64);
prq.add(6);
//print values
while (!prq.isEmpty()) {
System.out.print(prq.poll()+" ");
}
}
}
Per ulteriori informazioni, visitare:
È più comodo utilizzare [Collections.reverseOrder()] (https://docs.oracle.com/javase/8/docs/api /java/util/Collections.html#reverseOrder--) come argomento a PriorityQueue nella classe MaxHeap. –
Cosa intendi per più conveniente? Spiegheresti di più? – Mohammad
Penso che il metodo _reverseOrder_ sia più chiaro da leggere e capire cosa fa il confronto con '(x, y) -> y-x' –
Soprattutto da quando la domanda originale è stata fatta su google-collections, che ora è Guava. –
l'unico piccolo svantaggio è la mancanza di implementazione standard 'Deque' –
Non soddisfa il contratto Deque, quindi funziona come previsto. –