6
¿Por qué la mayoría de las colas de prioridad/montón se implementan como 0 siendo la prioridad más alta? Estoy asumiendo que estoy perdiendo algún principio matemático clave. Como estaba implementando mi propia cola de prioridad recientemente, me pareció más fácil escribir la función de inserción si la prioridad aumentaba con el valor entero, pero aparentemente las personas más inteligentes que yo creen que debería ir en la dirección opuesta.¿Por qué las colas de prioridad usan principalmente 0 como la prioridad más importante?
¿Alguna idea?
Aprendí algo nuevo. ¡Gracias! –
Esto es engañoso: todos los montoncitos que escuché sobre soporte * determinando * el mínimo en tiempo constante; pero * eliminar * el elemento mínimo (lo que hace que el segundo elemento más pequeño se convierta en el nuevo mínimo) siempre requiere el tiempo 'O (log (n))'. Esto es bastante fundamental; de lo contrario, podría usar ese montón para hacer un algoritmo de clasificación 'O (n)'. Las ventajas de rendimiento de un montón de fibonacci (sobre el montón binario simple) se encuentran en otras operaciones, no en estas dos operaciones estándar. –
¡Además, esta respuesta ni siquiera aborda la pregunta! Los montones de Fibonnacci también pueden ayudar a extraer el máximo en tiempo constante; es solo una convención. –