Cola de prioridad (Cola de prioridad)

/p/94155f9616bf

En la estructura de datos, la cola ordinaria es primero en entrar, primero en salir, pero a veces es posible que no queramos tener una regla tan fija, esperamos tener una cola de nivel de prioridad. Considere que en la vida real, algunas ventanas de cola de servicio dirán "El personal militar tiene prioridad según la ley" incluso si los pacientes son enviados al hospital en orden, los que están más gravemente enfermos a menudo también tendrán mayor prioridad; La programación de trabajos del sistema operativo también está relacionada con la prioridad...

Entonces, ¿podemos mejorar la cola? La cola tiene una cierta prioridad, lo que puede flexibilizar el procesamiento de algunas cosas y tareas. Por supuesto que es posible. La más básica se puede implementar basándose en una estructura lineal. Considere la complejidad del tiempo basada en una estructura lineal:

1. La cola es FIFO (primero en entrar, primero). Salir) primero en entrar, primero en salir La estructura de datos que se muestra corresponde a la escena de la cola en la vida. Las personas que van al frente siempre pasan primero y avanzan en orden.

2. La cola prioritaria es una cola especial. De la palabra "prioridad", podemos ver que existe un "fenómeno de salto de cola". Por ejemplo, cuando hacen cola en una estación de tren, algunas personas que tienen prisa se suben y pasan primero la inspección del billete. La cola de prioridad contiene al menos dos estructuras de datos para operaciones: insertar, que inserta elementos en la cola de prioridad (poner en cola); y eliminarMin (eliminar el más pequeño), que se utiliza para buscar y eliminar el elemento más pequeño en la cola de prioridad. (fuera de cola).

Estructura\Operación Cola y Cola

Estructura lineal ordinaria O(1) O(n)

Estructura lineal secuencial O(n) O(1)

La complejidad temporal de la cola de prioridad implementada por la estructura lineal ordinaria es O (n), porque el elemento de mayor prioridad debe eliminarse al quitar la cola, que es el elemento relativamente más grande (nota: el tamaño es relativo , podemos especificar reglas de comparación), por lo que debemos escanear toda la matriz para seleccionar la más grande. Para la operación de cola de estructura lineal secuencial, el orden original puede destruirse después de unirse a la cola, por lo que es necesario ajustar el orden actual.

Se puede ver que siempre hay operaciones con una complejidad temporal de O (n) usando estructuras lineales. ¿Existe una mejor manera de implementarla? Por supuesto que la hay, así que hablemos de Heap.

Estrictamente hablando, un montón también se llama montón binario porque su estructura es un árbol binario completo. Los montones generalmente se dividen en montones máximos y montones mínimos.

Propiedades del montón:

Estructural: un montón es un árbol binario que está completamente lleno, excepto la capa inferior. Los nodos en la capa inferior se completan de izquierda a derecha. un árbol se llama árbol binario completo. Es decir, la parte a la que le faltan nodos debe estar en la parte inferior derecha del árbol.

Orden del montón: dado que queremos encontrar el elemento mínimo rápidamente, el elemento mínimo debe estar en la raíz y cualquier nodo es más pequeño que sus descendientes. Este es el Min-Heap; Elemento máximo, entonces el elemento máximo debe estar en la raíz y cualquier nodo debe ser más grande que sus descendientes. Este es el montón máximo.

Montón máximo: el valor del nodo padre es mayor que el valor del nodo hijo

Montón mínimo: el valor del nodo padre es menor que el valor del nodo hijo

Dado que es un árbol binario completo, existe una cierta relación entre los índices de los nodos, por lo que podemos usar matrices para almacenar montones binarios, de la siguiente manera:

Si el almacenamiento comienza desde Índice 0, la relación de índice entre los nodos padre e hijo es la siguiente:

Cuando necesitamos agregar un nuevo dato a un montón máximo, nuestro montón se vuelve así.

En este momento, la adición de nuevos datos ya no cumple con la definición del montón máximo. Por lo tanto, debemos realizar una operación de desplazamiento hacia arriba en los datos recién agregados y colocarlos donde deberían estar. Durante la operación de cambio hacia arriba, comparamos los datos recién agregados con su nodo principal. Si es más grande que su padre, intercambie los dos.

En este punto hemos completado la operación de cambio hacia arriba de los elementos recién agregados.

Cuando sacamos un elemento del montón (es decir, la cola de prioridad). Colocamos el elemento en la parte superior del montón.

(Solo se puede sacar de la parte superior del montón)

En este momento, el montón no tiene parte superior, entonces, ¿qué debemos hacer? Solo necesitamos colocar el último elemento del montón en la parte superior del montón.

En este punto hemos completado la operación de desplazamiento hacia abajo después de hacer aparecer un elemento.

reemplazar: después de eliminar el elemento más grande, inserte un nuevo elemento

Implementación: primero puede extraer Max, luego agregar y realizar dos operaciones largas.

Implementación: reemplazar el elemento en la parte superior del montón y luego desplazarlo hacia abajo, una operación O(logn)

Insertar n elementos en un montón vacío uno por uno, la complejidad del algoritmo es O (nlogn), el proceso de heapify, la complejidad del algoritmo es O (n).

Heapify: organiza cualquier matriz en forma de montón.

Primero abstraiga una matriz en un montón. Este proceso se llama heapify.

Luego encontramos el primer nodo no hoja en el montón. La posición de este nodo es siempre el número de matrices dividido por 2, que es 27 en el índice 5. A partir de este nodo, para cada nodo. -nodo hoja Para los nodos hoja, realice una operación de cambio hacia abajo.

27 es más pequeño que su nodo hijo 51, por lo que los dos se intercambian.

A continuación nos fijamos en 20 en el índice 2. Primero, necesitamos intercambiar 20 con el mayor de sus dos nodos secundarios, 51.

La complejidad temporal de la apilamiento para cada nodo es O (logn) y la complejidad temporal total de la apilamiento para ese nodo es O (nlogn).

Proceso de derivación

El amontonamiento de nodos comienza desde la penúltima capa. Durante el proceso de amontonamiento, la cantidad de nodos que deben compararse e intercambiarse es proporcional a la altura k del nodo.

Entonces, la complejidad temporal de heapify() es O(n).

Una vez creado el montón, los datos de la matriz son un montón superior grande. Al intercambiar el elemento superior del montón, es decir, el elemento más grande, con el último elemento, el elemento más grande se colocará en la posición con índice n.

Este proceso es algo similar a la operación "eliminar el elemento superior del montón" anterior. Después de eliminar el elemento superior del montón, coloque el elemento con el subíndice n en la parte superior del montón. luego use el método de amontonamiento para eliminar los elementos restantes. Los siguientes n-1 elementos se reconstruyen en un montón. Este proceso se repite hasta que solo queda en el montón el elemento con índice 1 y se completa la clasificación.

Los problemas de Topk y Selectk se pueden resolver mediante clasificación rápida o cola de prioridad.

Cola rápida: O(n) espacio O(1)

Cola prioritaria: O(nlogk) espacio O(k)

Hay i en el cola prioritaria Sí, no es necesario conocer todos los datos a la vez y se procesa el flujo de datos.