1. Comprender los conceptos básicos
* Propiedad del montón: Un montón mantiene un orden específico. En un mínimo-montón, la clave del nodo principal es siempre menor o igual a las claves de sus hijos. En un máximo de montón, la clave del nodo principal es siempre mayor o igual a las claves de sus hijos.
* `priorityqueue` en Java: `Priorityqueue` implementa un montón min por defecto. Puede personalizarlo para que sea un Max-Heap utilizando un 'Comparador' personalizado.
* Complejidad del tiempo:
* `Agregar (elemento)`:o (log n) en promedio (donde n es el número de elementos en el montón)
* `eliminar ()` (elimina la raíz, min o max):o (log n)
* `peek ()` (devuelve la raíz):o (1)
* `contiene (elemento)`:o (n) en el peor de los casos. Los montones son * no * eficientes para buscar elementos arbitrarios.
* Construyendo un montón de una matriz:o (n)
2. Técnicas centrales y casos de uso
* Encontrar los k elementos más pequeños/más grandes: Esta es una aplicación de montón clásico.
* k más pequeño:
1. Cree un máximo de tamaño de tamaño `K` a partir de los primeros elementos` K` de su conjunto de datos.
2. Iterer a través de los elementos restantes. Si un elemento es más pequeño que la raíz del máximo-montón, retire la raíz e inserte el nuevo elemento.
3. Después de procesar todos los elementos, el Max-Weap contendrá los elementos más pequeños `K`.
* k más grande:
1. Cree un mínimo de tamaño de tamaño `K` a partir de los primeros elementos` K` de su conjunto de datos.
2. Iterer a través de los elementos restantes. Si un elemento es más grande que la raíz del Min-HeAap, retire la raíz e inserte el nuevo elemento.
3. Después de procesar todos los elementos, el Min-Heap contendrá los elementos más grandes 'K'.
`` `Java
import java.util.priorityqueue;
importar java.util.comparator;
import java.util.list;
import java.util.arrayList;
clase pública HeapExAMPLE {
Lista estática pública
Priorityqueue
para (int num:nums) {
if (minheap.size ()
} else if (num> minheap.peek ()) {
minheap.poll (); // Retire el más pequeño
minheap.add (num); // Agregar el nuevo elemento más grande
}
}
// Convierta el montón en una lista (opcional, para pedidos específicos)
List
klargest.sort (comparator.reverseorder ()); // clasificar descendiendo para más grande a más pequeño
regresar Klargest;
}
Lista estática pública
Priorityqueue
para (int num:nums) {
if (maxheap.size ()
} else if (num
maxheap.add (num); // Agregar el nuevo elemento más pequeño
}
}
// Convierta el montón en una lista (opcional, para pedidos específicos)
List
ksmallest.sort (comparador.naturalorder ()); // clasificar ascendiendo para más pequeño a más grande
regresar ksmallest;
}
public static void main (string [] args) {
int [] data ={5, 2, 9, 1, 5, 6};
int k =3;
List
System.out.println ("k más grande:" + más grande); // Salida:k más grande:[9, 6, 5]
List
System.out.println ("k más pequeño:" + más pequeño); // Salida:k más pequeño:[1, 2, 5]
}
}
`` `` ``
* fusionando k listas ordenadas:
1. Cree un mínimo de montón para almacenar el primer elemento en cada lista. Cada elemento en el montón debe almacenar el valor * y * el índice de la lista del que proviene.
2. Retire repetidamente el elemento mínimo del montón. Este es el siguiente elemento en la lista ordenada fusionada.
3. Si la lista de la que vino el elemento eliminado tiene más elementos, agregue el siguiente elemento de esa lista al montón.
4. Continúe hasta que el montón esté vacío.
`` `Java
import java.util.priorityqueue;
import java.util.list;
import java.util.arrayList;
clase pública MergeSortedlists {
El nodo de clase estática privada implementa comparable
valor int;
int listIndex;
int elementIndex;
Public Node (int value, int listindex, int elementindex) {
this.Value =value;
this.listIndex =listIndex;
this.elementIndex =elementIndex;
}
@Anular
public int Compareto (nodo otro) {
return integer.compare (this.Value, otro.value);
}
}
Lista estática pública
List
Priorityqueue
// Agregar el primer elemento de cada lista al montón
para (int i =0; i
minheap.add (nuevo nodo (lists.get (i) .get (0), i, 0));
}
}
while (! minheap.isempty ()) {
Nodo corriente =minheap.poll ();
fusedlist.add (current.Value);
int listIndex =current.listIndex;
int elementIndex =current.elementIndex;
// Agregar el siguiente elemento de la misma lista si existe
if (elementIndex + 1
}
}
regreso fusionlist;
}
public static void main (string [] args) {
Lista
lists.add (list.of (1, 4, 7));
lists.add (list.of (2, 5, 8));
lists.add (list.of (3, 6, 9));
List
System.out.println ("Lista fusionada:" + fusionado); // Salida:lista fusionada:[1, 2, 3, 4, 5, 6, 7, 8, 9]
}
}
`` `` ``
* Aplicaciones de cola prioritaria:
* Programación de tareas: Priorice las tareas basadas en la urgencia y ejecutarlas en orden.
* Algoritmos gráficos (Dijkstra, A*): Almacenamiento de nodos que se visitarán en función de su distancia estimada desde la fuente.
* Simulación de eventos: Eventos de proceso en orden cronológico.
3. Consideraciones importantes para grandes datos
* Gestión de memoria: Si su conjunto de datos es * extremadamente * grande y no encaja en la memoria, considere:
* clasificación externa (clasificar con montones): Romper los datos en fragmentos más pequeños que se ajustan en la memoria, ordene cada fragmento (usando montones u otros métodos) y luego fusionen los fragmentos ordenados usando un montón. Esto implica leer y escribir datos en el disco.
* Algoritmos de transmisión: Algoritmos diseñados para procesar datos en una sola pasada, minimizando el uso de la memoria. Si bien un montón puro puede no ser adecuado para la transmisión en todos los casos, puede usar técnicas como el muestreo de yacimientos junto con montones.
* Comparador personalizado: Para objetos complejos, implementa un `Comparador` que define cómo se deben comparar sus objetos en el montón.
* Recolección de basura: Los grandes montones pueden ejercer presión sobre el recolector de basura. Tenga en cuenta la creación y eliminación de objetos para evitar cuellos de botella de rendimiento.
* Perfil: Use herramientas de perfil para identificar puntos de acceso de rendimiento en su código. Esto puede ayudarlo a determinar si las operaciones de montón son el cuello de botella y si necesita optimizarlos más.
* tipos primitivos (cuando sea posible): Si está trabajando con tipos primitivos (por ejemplo, `int`,` double`), considere usar un `int []` o `double []` como el almacenamiento subyacente para su montón, en lugar de objetos `enteros` o` double`. Esto puede reducir la sobrecarga de la memoria y mejorar el rendimiento. Luego implementaría la lógica del montón usted mismo (usando índices de matriz). Esto solo es necesario en escenarios extremadamente sensibles al rendimiento.
* Pre-asignación: Si conoce el tamaño máximo aproximado de su montón por adelantado, prealifique el 'priorityqueue' con esa capacidad. Esto puede evitar el cambio de tamaño de las operaciones, que pueden ser costosas.
Ejemplo:priorizar las entradas de registro
Imagine que está procesando un archivo de registro grande y necesita extraer las entradas de registro más críticas `n` basadas en una puntuación de gravedad.
`` `Java
import java.util.priorityqueue;
importar java.util.comparator;
import java.util.list;
import java.util.arrayList;
Logentry de clase {
Mensaje de cadena;
int severidad;
public logentry (mensaje de cadena, int severidad) {
this.message =Mensaje;
this.severity =severidad;
}
@Anular
public String toString () {
Devolver "logentry {" +
"Message ='" + Mensaje +' \ '' +
", severidad =" + severidad +
'}';
}
}
clase pública loganalyzer {
Lista estática pública
Priorityqueue
for (logentry log:logs) {
if (minheap.size ()
} else if (log.getseverity ()> minheap.peek (). getSeverity ()) {
minheap.poll ();
minheap.add (log);
}
}
Lista
criticAllogs.sort (comparador.comparingint (logentry ::getSeverity) .Reversed ());
regresar críticas;
}
public static void main (string [] args) {
Lista
logs.add (nuevo logentry ("error de baja prioridad", 1));
logs.add (nuevo logentry ("advertencia de prioridad media", 5));
logs.add (nuevo logentry ("Error crítico - bloqueo del sistema", 10));
logs.add (nuevo logentry ("Otro evento de baja prioridad", 2));
logs.Add (nuevo logentry ("Problema de red de alta prioridad", 8));
logs.Add (nuevo logentry ("problema de la base de datos de prioridad media", 6));
int n =3;
Lista
System.out.println ("Logs más críticos:" + crítico);
// Salida:Logios más críticos:[logentry {Message ='Error crítico - System Crash', Severity =10}, LogEntry {Message ='Problema de red de alta prioridad', Severity =8}, logentry {Message ='Problema de base de datos de prioridad media', Severity =6}]
}
}
`` `` ``
En resumen:
Los montones son poderosos para encontrar valores extremos (min/max) y priorizar elementos en un conjunto de datos. Al tratar con grandes cantidades de datos, tenga en cuenta el uso de la memoria, considere las técnicas de clasificación externa si es necesario, y perfile su código para identificar y abordar los cuellos de botella de rendimiento. La clase `priorityqueue` en Java es un punto de partida conveniente, pero es posible que deba personalizarla o implementar su propia lógica de montón para casos de uso específicos y restricciones de memoria.
> listas) {
> lists =new ArrayList <> ();