Notes

• 1 + 1/2 + 1/4 + 1/8 …. = 2
• Si siempre divido en K, hay un logk(n)

Truquitos para calcular costo amortizado:

• costo total / cant de operaciones
• Acotar (Ahorro/gasto) (en el ejemplo de cola con dos pilas, x ej. uso ahorro 3 y gasto 1 por cada inserción)
• Skip list infinita

→ imp la cola con dos pilas: costo amortizado O(1)

• No olvidar que en heaps solo se puede hacer remove_max

→ imp heapify

→ imp en un B+ tree definir el criterio de si el igual es a la izquierda o a la derecha

[12] Queremos implementar una pila especial que soporte las siguientes operaciones: push(elem) // Agrega un elemento al stack. (idem a una pila común) pop() // Devuelve el último elemento y lo elimina del stack. (idem a una pila común) top() // Devuelve el elemento al tope de la pila, no lo remueve. (idem a una pila común) get_min() // Devuelve el mínimo elemento del stack. (no lo remueve) Todas (toooodas) las operaciones deben ser O(1). Indique qué estructura(s) de datos usaría y cómo implementaría push, pop, top y get_min usando dichas estructuras.

Hago una pila en la que voy guardando tuplas del valor y el mínimo actual, así cuando hago un pop y me quiero fijar el mínimo, solo veo el último mínimo guardado

Podes hacerlo también con otra pila en la que vas guardando los mínimos