Algoritmos y Estructuras de Datos (VJ1215)
Curso 2022/2023
Algoritmos y Estructuras de Datos (VJ1215)
Curso 2022/2023
| insertar | eliminarMínimo | consultarMínimo | |
|---|---|---|---|
| (i) vector no ordenado | O(1) | O(n) | O(1) |
| (ii) vector ordenado | O(n) | O(1) | O(1) |
| (iii) lista enlazada no ordenada | O(1) | O(n) | O(1) |
| (iv) lista enlazada ordenada | O(n) | O(1) | O(1) |
| (v) árbol binario de búsqueda | O(n) | O(n) | O(1) |
| (vi) árbol AVL | O(log n) | O(log n) | O(1) |
| (vii) montículo binario | O(log n) | O(log n) | O(1) |
Las implementaciones (i) a (iv) se estudiaron en el tema 2.
En las implementaciones (v) y (vi) mantendríamos un atributo adicional que tenga el valor mínimo, para que la operación consultarMínimo tenga coste O(1). En la operación que inserta un nuevo dato actualizaríamos ese atributo si el nuevo dato es menor. En la operación que elimina cualquier dato tendríamos que actualizar ese atributo buscando el nuevo mínimo en caso de que el dato eliminado fuese el mínimo. La operación eliminarMínimo se podría implementar haciendo uso de la operacion que elimina cualquier dato.
Un resultado interesante aquí, que algunos autores explican mal, es que con un montículo binario no mejoramos el coste en el peor caso que se puede obtener con un árbol AVL para esas operaciones (lo que mejoramos notablemente son las constantes que afectan al tiempo).