¿Existe un algoritmo para fusionar 2 montones máximos en un montón mínimo con una complejidad de tiempo menor que O (n)?
De ninguna manera.
Piénselo: un montón máximo tiene el mayor valor en la parte superior. El valor más pequeño estará en el nivel más bajo en alguna parte. Consideremos un árbol completo (por lo que todos los elementos de nivel más bajo están en el mismo nivel).
- ¿Cómo se siente Bram Cohen al haber creado accidentalmente un algoritmo para el cifrado totalmente homomórfico?
- ¿Cómo puedo diseñar una función hash que elija aleatoriamente 16 bits de un número de 32 bits?
- Cómo hacer para vender con éxito el algoritmo de negociación de fx
- ¿Cómo combina ACM ICPC invertir en diversidad y mantener alta la barra de entrada?
- Cómo contar el número de n rutas de borde que comienzan desde el nodo u en un DAG (gráfico acíclico dirigido)
Para un árbol con 4 niveles, tenemos 1 artículo en el 1er nivel, 2 en el 2do, 4 en el 3er, 8 en el 4to. Para n elementos en un montón máximo completo, (n + 1) / 2 de ellos están en el nivel más bajo.
Sin siquiera hablar sobre cuánto tiempo tomaría llegar a esos elementos, sin siquiera considerar cómo entra en juego el segundo montón, y sin preocuparse por construir realmente un montón, solo considerando la pregunta de qué elemento debería estar en la raíz de un elemento. min montón significa que tienes que comparar (n + 1) / 2 elementos. Eso significa que ya tienes O (n), no importa cómo lo cortes. Puede empeorar a partir de ahí, pero no puede mejorar.
