Problema complejidades

[IgnacioHqz]

Hola, estoy tratando de pensar cómo hacer la parte de Happiness, pero estoy teniendo problemas con la complejidad que se pide. Se supone que si se hace una actualización de un valor, si es un MIN heap, hay que revisar hacia arriba si es que el valor es menor que el padre (algo asi como siftup), pero el problema es que eso sería O(log(n)) + O(n) para encontrar el nodo, y me pasaría de la complejidad. Tal vez no estoy pensando bien la estructura a utilizar? Si me pudieran ayudar lo agradeceria mucho!

[Segismundios]

Holaa @IgnacioHqz. Tal y como mencionas, la complejidad del siftup es O(log(n)), con lo que la complejidad total del evento quedaría en O(log(n)+n). Pero recuerda que cuando trabajamos con notación Big-O, nos enfocamos en el término que crece más rápido a medida que el tamaño de n aumenta. En este caso, el término O(n) crece mucho más rápido que O(log(n)) para un n muy grande, por lo que O(log(n)+n) se simplifica a O(n).

[IgnacioHqz]

Perfecto! Me había olvidado de que se mantenía el mayor, gracias por la aclaración!
También quisiera aprovechar la instancia para consultar sobre el mismo tema de complejidades: Sucede que con el fin de que en la parte MEDIANS la complejidad sea O(1), lo único que se me ocurre que sirva para poder solamente sacar la menor mediana, y mayor mediana y no tener que buscarlas era haciendo un Heapsort, pero el problema es que Heapsort es O(nlog(n)) y no se podría colocar despues de un ENTER ni en HAPPINESS ya que se pasaría en la complejidad, y no sabría en que momento poder hacerlo, o podría ser que no lo esté pensando bien? También me sucede algo parecido con la parte de FESTIVAL, ya que para que la complejidad sea O(s) solamente habría que sacar el mas triste y el mas feliz al inicio y final de una cola, haciendo un Heapsort de los pinguinos, pero tambien afectaria la complejidad. Cualquier comentario sirve! ya que la verdad estoy algo complicado jajaj Gracias!