El entrevistador le preguntará nuevamente sobre su cola de prioridad. Por favor, envíele este artículo.

Si hay muchos eventos en el sistema de eventos que diseña y cada evento tiene un valor de peso diferente definido, el sistema necesita priorizar los eventos con pesos más altos. Aquí debe usar una cola de prioridad. En el artículo, aprenderemos las formas comunes de implementar colas de prioridad

Antes de la implementación, primero debemos definir la API de la cola de prioridad. La cola de prioridad es una estructura de datos abstracta que aún podemos modificar en función de. API de cola que utilizamos anteriormente, si necesita conocer la implementación de la cola anterior, puede consultar "La temporada de entrevistas está aquí, ¿está seguro de que desea revisar la estructura de datos?" poner en cola y quitar la cola es la forma principal que necesitamos para implementarlo, y también es el método central de la cola de prioridad

La implementación más simple de la cola de prioridad se puede encontrar en "La temporada de entrevistas está aquí, estoy seguro No revisaré la estructura de datos". 》 La implementación de la pila en "Enqueue" es consistente con el método push de la pila. Para quitar la cola, puede consultar la implementación de la clasificación por selección, recorrer la matriz y encontrar el valor máximo. e intercambiarlo con el último elemento de la matriz, y luego eliminarlo;

Aquí solo se implementan colas de prioridad de longitud fija ¿Cómo lograr la expansión automática? También puede consultar este artículo "La temporada de entrevistas está aquí, ¿está seguro de que desea revisar la estructura de datos?"; la complejidad temporal de la puesta en cola basada en matrices desordenadas es O (1), y la complejidad temporal de la puesta en cola es O (n)

La implementación basada en una matriz ordenada garantiza que la matriz esté en orden al ingresar a la cola, de modo que el valor máximo se pueda eliminar directamente al quitar la cola. El proceso de inserción es similar a la operación de clasificación por inserción;

La complejidad temporal de la puesta en cola es O (n) y la complejidad temporal de la puesta en cola es O (1)

La implementación basada en la lista vinculada es similar a la anterior. si está interesado, puede implementarlo usted mismo

En un montón binario, cada nodo será mayor o igual que sus nodos secundarios, y también se convertirá en un montón en orden, el nodo raíz es el nodo más grande;

Representación del montón binario:

Puntos clave:

En un montón binario, la posición del nodo padre del nodo k es k/2 y Las posiciones de los dos nodos secundarios son 2k y 2k+1. En base a esto, podemos usar una matriz para representar el montón binario y encontrar el nodo principal y el nodo secundario del nodo moviendo el subíndice de la matriz

En el elemento Durante las operaciones de inserción y eliminación, el orden del montón se destruirá, por lo que debemos realizar algunas operaciones para garantizar que el montón vuelva a estar ordenado. Cuando la prioridad de un; el nodo aumenta, necesitamos restaurar el orden del montón de abajo hacia arriba (hundimiento) cuando la prioridad de un nodo cae, necesitamos restaurar el orden del montón de arriba a abajo (flotando hacia arriba); Encuentre la posición k/2 del nodo principal según el nodo actual k y compare el actual. Si el nodo y el nodo principal son más grandes que el nodo principal, se intercambian hasta que se encuentra un nodo principal que sea más grande que el nodo actual. o ha flotado al nodo raíz

Todos los códigos fuente de este artículo se han colocado en el almacén de github/silfully9527/JavaCore

Puede haber más o menos deficiencias y errores en el artículo Si tiene sugerencias u opiniones, puede compartirlas en los comentarios.

Finalmente, escribir no es fácil, por favor no me utilices para nada. Espero que a tus amigos les guste, comenten y sigan a Sanlian, porque estas son todas las fuentes de motivación para compartir.