heaps - Implementación de Java para Min-Max Heap?

heap vs priority queue

Question

¿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) ?

Answer 1

¿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.

Answer 2

De Guava: MinMaxPriorityQueue .

Answer 3

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.

Answer 4

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:

• https://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/MaxHeapWithPriorityQueue.java

• https://github.com/m-vahidalizadeh/foundations/blob/master/src/data_structures/MinHeapWithPriorityQueue.java

Answer 5

La clase java.util.TreeSet .

Answer 6

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;
}