Quiero usar una cola prioritaria en un problema. Creo que implementar una cola prioritaria usando una matriz es más fácil que usar un montón. ¿Qué piensas y por qué?

Quiero usar una cola prioritaria en un problema. Creo que implementar una cola prioritaria usando una matriz es más fácil que usar un montón. ¿Qué piensas y por qué?

Creo que puedes hacerlo mejor una vez que dejas de pensar de manera tan abstracta.

En la vida real, la mayoría de las colas de prioridad solo se extienden sobre un puñado de valores de prioridad reales, que generalmente son (o se pueden asignar fácilmente) a un rango de enteros [matemática] [0..k) [/ matemática]. Estoy bastante seguro de que cualquiera de los desarrolladores de software a los que he asesorado a lo largo de los años respondería instantáneamente a esta descripción con:

¡Oh, solo use una matriz de colas, donde el índice de la matriz es la prioridad!

La complejidad del tiempo es extremadamente favorable. Las operaciones Insert / delete / isEmpty en las colas individuales son [math] \ Theta (1) [/ math], a menos que esté haciendo algo realmente extraño, y la selección de la cola por prioridad (básicamente “que es el primer no vacío queue? ”) es [math] \ Theta (k) [/ math], para una complejidad general get_next_item de [math] \ Theta (k) [/ math], donde [math] k [/ math] es bastante pequeño.

Más importante aún, la complejidad de la implementación es sustancialmente menor que con una sola matriz o un montón, si tiene que implementar todo desde cero. Una cola de búfer circular o lista enlazada es mucho más fácil de obtener que un montón.

¡Buena suerte!

Implementar una cola prioritaria utilizando una matriz de una manera ingenua es definitivamente más fácil de implementar que un montón, pero se ejecutará mucho más lentamente si sus matrices son muy grandes.

Supongamos que implementa una matriz de una manera ingenua.

Cada operación push () tomará tiempo [matemático] \ Theta (1) [/ matemático] (amortizado), pero cada pop () tomará tiempo [matemático] \ Theta (n) [/ matemático], donde n es el tamaño de la cola de prioridad. Esto es porque tienes que encontrar el máximo y luego cambiar todo.

Ahora, supongamos que usa un montón. Cada push () y pop () toman tiempo [math] \ Theta (\ log n) [/ math]. Ahora, digamos [matemáticas] n = 1024 [/ matemáticas]. Luego, un algoritmo [matemático] \ Theta (n) [/ matemático] tomará aproximadamente 1024 operaciones, mientras que un [matemático] \ Theta (\ log n) [/ matemático] tomará solo 10 operaciones.