priority heaps data computing java data-structures minmax-heap

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



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:



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