heaps - Implementación de Java para Min-Max Heap?
heap vs priority queue (6)
¿Qué tal com.aliasi.util.MinMaxHeap ? Esto es parte de LingPipe ; desafortunadamente, la licensing puede ser un problema.
Ver este documento relacionado .
Sin embargo, no implementa decreaseKey o increaseKey.
¿Conoces una biblioteca popular (colecciones Apache, Google, etc.) que tiene una implementación Java confiable para un montón mínimo, que es un montón que permite ver su valor mínimo y máximo en O(1)
y eliminar un elemento en O(log n)
?
De Guava: MinMaxPriorityQueue
.
En lugar de un montón máximo-mínimo, ¿podrías usar dos instancias de java.util.PriorityQueue contengan los mismos elementos? La primera instancia pasaría un comparador que pone el máximo a la cabeza, y la segunda instancia usaría un comparador que pone el mínimo a la cabeza.
La desventaja es que agregar, eliminar, etc. tendría que realizarse en ambas estructuras, pero debería satisfacer sus requisitos.
Java tiene buenas herramientas para implementar pilas mínimas y máximas. Mi sugerencia es usar la estructura de datos de cola de prioridad para implementar estos montones. Para implementar el montón máximo con cola de prioridad, pruebe esto:
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()+" ");
}
}
}
Para implementar el montón mínimo con cola de prioridad, intente esto:
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()+" ");
}
}
}
Para mayor información por favor visite:
La clase java.util.TreeSet .
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;
}