Complejidad de LEAVE

[vichoassadi]

He estado dándole 1000 vueltas a intentar crear una estructura de datos en la que la inserción, extracción y lectura del mínimo, mediana y máximo sean O(log(n)). Sin embargo al momento de eliminar el pingüino con menor felicidad, no logro encontrar una manera de encontrar el siguiente pingüino con menor felicidad sin tener que recorrer un heap entero (estoy ocupando varios heaps), lo que sería O(n), o solo el último nivel de un Max-Heap (O(n/2) = O(n)).

Con esto vengo hacer un llamado de ayuda, en el que vengo a preguntar si es que de verdad existe una manera hacerlo únicamente con heaps y punteros de forma que se cumplan todas las restricciones de complejidad. Le llevo dando vueltas cerca de 15 horas y no logro llegar a una solución.

Con un sí o no me basta. Muchas gracias.