Unidad Didáctica 1:

ESTRUCTURAS DINÁMICAS DE
DATOS

Algoritmos y Estructuras de Datos

Nombre de la asignatura

[Link]
ÍNDICE Contenido
1. INTRODUCCIÓN........................................................................................ 3
2. OBJETIVOS................................................................................................ 5
2.1 ESPECÍFICOS ........................................................................................... 5
3. TEMA 1: REPASO DE TIPOS DE DATOS ..................................................... 6
3.1. TIPOS DE DATOS BÁSICOS VS. TIPOS DE DATOS ABSTRACTOS (TDA)............... 6
3.2. ESTRUCTURAS DE DATOS (EEDD) .......................................................... 9
3.3. LISTAS ENLAZADAS ............................................................................ 13
3.4. PILAS .............................................................................................. 34
3.5. LISTAS ENLAZADAS ............................................................................ 37
3.6. ÁRBOLES ......................................................................................... 47
3.7. GRAFOS .......................................................................................... 54
3.8. TABLAS DE HASH .............................................................................. 70
3.9. MONTÍCULOS ................................................................................... 74
3.10. COLAS DE PRIORIDAD (PRIORITY QUEUES) .............................................. 94
3.11. CONJUNTOS (SETS).......................................................................... 101
4. BIBLIOGRAFÍA....................................................................................... 108

[Link]
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

1. Introducción

¡Bienvenido a la asignatura de Algoritmos y Estructuras de datos!

Como bien sabes, los tres pilares fundamentales del desarrollo de sistemas son el diseño, la
programación (o desarrollo) y el almacenamiento. Es en este segundo de estos pilares en el que
cobra mayor importancia el estudio de los algoritmos y las estructuras de datos. Siendo estas
herramientas indispensables para cualquier programador.

Esta asignatura está dirigida a estudiantes que ya disponen de conocimientos básicos de

programación, conocimientos que se dan por sentados y se asumen como conocimientos
previos que ya adquiriste en las asignaturas de Fundamentos de la Programación I y
Fundamentos de la Programación II cursadas durante el primer y segundo cuatrimestre de la
titulación de Algoritmos y Estructuras de datos.

La selección de la estructura de datos adecuada para almacenar la información en la memoria

principal es un aspecto crítico, especialmente en función del problema específico que debamos
abordar. Esto se vuelve más crucial cuando se manejan grandes volúmenes de datos y se
necesita que el sistema responda eficientemente. En relación con el tercer pilar, que se refiere
al almacenamiento, es importante destacar que los diferentes sistemas de bases de datos
utilizan una variedad de estructuras de datos para gestionar sus operaciones internas. Por
ejemplo, emplean árboles para consultas y aprovechan índices hash para mejorar el rendimiento
de las búsquedas, el acceso a la memoria secundaria y la manipulación de datos, especialmente
en el caso de bases de datos basadas en el modelo clave-valor.

Si bien en esta asignatura vamos a trabajar con el lenguaje de programación Python, las
estructuras de datos son herramientas disponibles en todo lenguaje de programación. Por lo
que el correcto entendimiento de estas, nos permitirá aplicar nuestros conocimientos sobre
cualquier otro lenguaje. Estas estructuras de datos nos permiten almacenar o agrupar un
conjunto de elementos o datos, de forma que nos facilitan su gestión enormemente.

Es importante que entiendas que no existe una estructura de datos mejor que otras, cada una
tiene sus pros y sus contras. Es por este motivo que comprendas el funcionamiento de cada una
para poder utilizar la más adecuada en cada caso.

En muchas ocasiones, te encontrarás con la necesidad de trabajar con más de una estructura de
datos a la vez, combinándolas en un mismo algoritmo (en memoria principal) y los datos
almacenados físicamente en disco (bien sea en una base de datos o en un archivo). Trataremos
estos contenidos en los temas 1 y 2 en los que te presentaré y analizaremos las distintas
estructuras de datos y su modelado.

A la hora de diseñar y seleccionar los algoritmos, deberemos observar distintos factores que
condicionan su programación, tales como la eficiencia (referido a las técnicas, recursos y

[Link]
© Universidad Alfonso X el Sabio 3
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

tiempos utilizados), la manera en que lo estructuramos o escribimos (legibilidad del código y

organización de este), las nomenclaturas utilizadas, el uso de buenas prácticas y la
documentación del código. Para el control de buena parte de estos factores podemos apoyarnos
en el uso de un IDE (entorno de desarrollo integrado) y nuestra experiencia como
programadores. Sin embargo, en lo que atañe a la eficiencia de los algoritmos, debemos
comprender cómo analizarlos y medir esta eficiencia de modo que nos permita analizarla y
medirla para poder comparar con criterio algoritmos que usen diferentes técnicas para resolver
el mismo problema. Trataremos estos contenidos en los temas 3 y 4.

Finalmente, en los temas 5 y 6, aplicarás los conocimientos adquiridos en los temas anteriores
para la resolución de problemas y el diseño de nuevos algoritmos.

En resumen, a lo largo de esta asignatura conocerás las diversas estructuras de datos y

algoritmos básicos y aprenderás a analizarlos bajo determinados criterios, lo que te permitirá
seleccionar las herramientas más adecuadas a la solución de los problemas que se te planteen.
Para ello, encontrarás una guía de ejercicios al final de cada capítulo para que comiences a
incorporar estos recursos y desarrolles el pensamiento algorítmico.

Ten en cuenta
Dependiendo del problema y las circunstancias que lo rodean,
deberemos seleccionar la o las estructuras de datos más adecuadas, así
como implantar los algoritmos más eficientes.

[Link]
© Universidad Alfonso X el Sabio 4
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

2. Objetivos
2.1 Específicos

En esta unidad se establecen dos objetivos principales:

 Comprender la diferencia entre tipos de datos abstractos y estructuras de datos

dinámicas.

 Reconocer las ventajas y desventajas de las estructuras de datos dinámicas en la

programación.

 Explicar cómo funcionan las listas enlazadas simples y su importancia en el

almacenamiento y manipulación de los datos

 Implementar listas enlazadas simples en un entorno de programación, utilizando un

lenguaje de programación específico.

 Resolver ejercicios prácticos que involucren el uso de listas enlazadas simples para
comprender su aplicación en situaciones reales

Estos conceptos son fundamentales para comprender las estructuras de datos y los
algoritmos en profundidad

[Link]
© Universidad Alfonso X el Sabio 5
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

3. Tema 1: Repaso de tipos de datos

3.1. Tipos de datos básicos Vs. tipos de datos abstractos (TDA)

Hasta el momento, seguramente hayas estado utilizando tipos de datos básicos y algunos tipos
de datos abstractos. Vamos a hacer un breve repaso.

Los tipos de datos básicos, los “de toda la vida”, con los que hemos trabajado siempre para
representar datos básicos:

 Integer: representan datos numéricos positivos y negativos incluyendo el cero, es

decir, los números enteros.

 Float: representan datos numéricos reales o racionales (los números “con

decimales”).

 String: representan caracteres o cadenas de caracteres alfanuméricos.

 Boolean: o lógicos, representan valores del tipo TRUE o FALSE (verdadero o falso),
ampliamente utilizados en operaciones condicionales o de comparación.
Por otro lado, tenemos los tipos de datos abstractos (TAD) también conocidos como
colecciones que también conocéis del curso pasado:

 List (listas): colecciones ordenadas y mutables (modificables) de elementos. Los

elementos pueden ser de cualquier tipo de datos. Por ejemplo: [1,2,3], [“perro”,
“gato”, “pez”]

 Tuplas (tuples): similares a las listas, pero inmutables (no se pueden modificar una
vez creadas). Las encontrarás también por el nombre de registros. Por ejemplo:
(1,2,3)

 Set (conjuntos): colecciones no ordenadas de elementos únicos. Solemos utilizarlos

para realizar operaciones matemáticas de conjuntos, como la unión, intersección y
la diferencia. Por ejemplo: {1,2,3}

 Dict (diccionarios): colecciones de pares clave-valor (key-value), en las que cada

valor está asociado a una clave única. Por ejemplo: {“dni”: “123456789D”,
”nombre”: “Pepito”, “apellidos”: “de los Palotes}

[Link]
© Universidad Alfonso X el Sabio 6
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Veamos una tabla comparativa de las características de los tipos de datos abstractos o
colecciones:

Clave-
TAD Ejemplo Ordenada Mutable Indexable
Valor
[1,2,3] Sí Sí Sí No
Lista

(1,2,3) Sí No Sí No
Tupla
{“id”:1, No Sí No Sí
Diccionario “nombre”:”Pepe”}
{1, 2, 3} No Sí No No
Conjunto

Tabla 1 Comparativa de tipos de datos abstractos

Como puedes observar, cada colección o tipo de dato abstracto tiene sus propias características,
lo cual debemos aprovechar a nuestro favor adecuando su uso para obtener la solución más
adecuada a cada contexto.

Todos los tipos de datos abstractos, excepto las tuplas – debido a su inmutabilidad – disponen
de sistemas que nos permiten añadir, buscar y eliminar elementos dentro de estos. Recordemos
algunos métodos que nos proporciona Python:

Listas (List):

 append(item): Agrega un elemento al final de la lista.

 extend(iterable): Extiende la lista agregando elementos de un iterable.

 insert(index, item): Inserta un elemento en la posición especificada.

 remove(item): Elimina la primera aparición de un elemento de la lista.

 pop(index): Elimina y devuelve el elemento en la posición especificada.

 index(item): Devuelve el índice de la primera aparición de un elemento.

 count(item): Cuenta cuántas veces aparece un elemento en la lista.

 sort(): Ordena la lista en su lugar.

 reverse(): Invierte la lista en su lugar.

 clear(): Elimina todos los elementos de la lista.

[Link]
© Universidad Alfonso X el Sabio 7
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Diccionarios (Dictionary):

 keys(): Devuelve una vista de las claves del diccionario.

 values(): Devuelve una vista de los valores del diccionario.

 items(): Devuelve una vista de pares clave-valor del diccionario.

 get(key, default): Devuelve el valor asociado con la clave especificada o un valor

predeterminado si la clave no existe.

 pop(key, default): Elimina y devuelve el valor asociado con la clave especificada o

un valor predeterminado si la clave no existe.

 popitem(): Elimina y devuelve un par clave-valor arbitrario del diccionario.

 clear(): Elimina todos los elementos del diccionario.

Conjuntos (Set):

 add(item): Agrega un elemento al conjunto.

 remove(item): Elimina un elemento del conjunto; genera un error si el elemento no

está presente.

 discard(item): Elimina un elemento del conjunto si está presente; no genera un error

si el elemento no existe.

 pop(): Elimina y devuelve un elemento arbitrario del conjunto.

 clear(): Elimina todos los elementos del conjunto.

 union(other_set): Devuelve un nuevo conjunto que es la unión de dos conjuntos.

 intersection(other_set): Devuelve un nuevo conjunto que es la intersección de dos

conjuntos.

 difference(other_set): Devuelve un nuevo conjunto que contiene elementos que

están en el conjunto actual pero no en otro conjunto.

 symmetric_difference(other_set): Devuelve un nuevo conjunto con elementos que

están en uno de los conjuntos pero no en ambos.

[Link]
© Universidad Alfonso X el Sabio 8
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Estos tipos de datos básicos y tipos de datos abstractos son las piezas con las que podemos
construir las estructuras de datos. Comencemos.

3.2. Estructuras de Datos (EEDD)

Una estructura de datos es como un armario o estantería donde guardas tus cosas. Dependiendo
de qué quieras guardar y cómo quieras acceder a esas cosas, elegirás diferentes tipos de
armarios.

Por ejemplo:

• Si tienes muchos zapatos, quizás quieras un zapatero donde los organices por color o
por tipo. En programación, esto sería como una "lista" donde guardas elementos en un
orden específico.
• Si tienes llaves y quieres acceder rápidamente a cada una según su función (llave de la
casa, del coche, del trabajo...), quizás uses un llavero con etiquetas. Esto se asemejaría
a lo que llamamos "diccionario" o "mapa" en programación, donde guardas cosas según
una clave y un valor.
En resumen, una estructura de datos es como un contenedor que elegimos según cómo
queremos guardar y acceder a la información. Hay muchos tipos, y cada uno tiene sus ventajas
según lo que necesites hacer.

Es como escoger el mejor lugar para guardar tus cosas dependiendo de lo que son y cómo las
usarás. ¡Espero que esto te haya ayudado a entenderlo mejor!

Expresándolo de una forma un poco más formal, una estructura de datos es una forma
organizada y específica de almacenar y organizar datos en una computadora para que puedan
ser utilizados de manera eficiente. Estas estructuras permiten a los datos ser procesados,
accedidos y transferidos de manera efectiva. Son implementaciones concretas de los Tipos de
Datos Abstractos (TDAs) y otras formas de organizar la información. Son esenciales para crear
programas eficientes y efectivos.

Definición
Una estructura de datos es una forma organizada y específica de
almacenar y organizar datos en una computadora para que puedan ser
utilizados de manera eficiente. Son implementaciones concretas de los
TDAs. Estas estructuras permiten a los datos ser procesados, accedidos y
transferidos de manera efectiva.

[Link]
© Universidad Alfonso X el Sabio 9
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Las estructuras de datos varían en términos de eficiencia para diferentes tipos de operaciones,
por lo que la selección adecuada es crucial en la programación. Algunas de las estructuras de
datos más comunes incluyen listas, pilas, colas, árboles y grafos.

La elección de una estructura de datos a menudo depende de la naturaleza del problema y de

las operaciones que se quieran realizar con los datos (por ejemplo, inserción, búsqueda,
eliminación, entre otros).

3.1.1. Operaciones básicas

Las estructuras de datos generalmente soportan un conjunto de operaciones básicas que nos
permiten interactuar con los datos almacenados dentro de ellas. Estas operaciones pueden
variar ligeramente dependiendo de la estructura específica, pero existen algunas de las
operaciones comunes que se encuentran en diversas estructuras:

1. Inserción: Añadir un nuevo elemento a la estructura.

2. Eliminación: Quitar un elemento de la estructura.
3. Búsqueda: Localizar un elemento en la estructura para consultar o modificar su valor.
4. Actualización: Cambiar el valor de un elemento existente.
5. Travesía o recorrido: Pasar por todos los elementos de la estructura, ya sea para
procesarlos o simplemente revisarlos.
6. Ordenamiento: Organizar los elementos de la estructura según algún criterio definido.
7. Acceso: Obtener un elemento específico basado en su posición o clave.
8. Tamaño: Determinar la cantidad de elementos que hay en la estructura.
9. Verificación de vacío: Checar si la estructura tiene o no elementos.
Estas operaciones básicas pueden manifestarse de diferentes maneras según la estructura de
datos en cuestión. Por ejemplo, en una pila, las operaciones de inserción y eliminación se
conocen como "push" y "pop", mientras que en una lista o un arreglo podríamos hablar de
"añadir" y "eliminar". En un mapa o diccionario, las operaciones de inserción, eliminación y
acceso se realizan generalmente a través de claves únicas asociadas a cada elemento.

El diseño y elección adecuados de las estructuras de datos y sus operaciones son fundamentales
para asegurar que los programas y sistemas funcionen de manera eficiente y efectiva.

3.1.2. Estructuras de datos estáticas Vs. dinámicas

La principal diferencia entre estructuras estáticas y dinámicas radica en cómo manejan la
memoria y cómo se adaptan al cambio de tamaño durante la ejecución de un programa.

[Link]
© Universidad Alfonso X el Sabio 10
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Veamos las características de ambos tipos en cuanto al manejo de la memoria:

- Estructuras Estáticas:
o Ejemplos: Arreglos (Arrays) en muchos lenguajes de programación. Ya las
conoces de sobra, por lo que no vamos a entrar en ellas en esta asignatura.
o Memoria Contigua: Los elementos en estructuras estáticas (como los arreglos)
se almacenan en bloques contiguos de memoria.
o Tamaño Predefinido: Al crear una estructura estática, necesitas definir su
tamaño de antemano. Una vez definido, este tamaño no cambia.
- Estructuras Dinámicas:
o Ejemplos: Listas enlazadas, árboles, grafos.
o Memoria No Contigua: Los elementos en estructuras dinámicas (como listas
enlazadas) no necesariamente están ubicados uno al lado del otro en
memoria. Están conectados a través de referencias o punteros.
o Tamaño Variable: Estas estructuras pueden cambiar de tamaño durante la
ejecución del programa. Por ejemplo, puedes añadir o eliminar nodos de una
lista enlazada.

En lo referente a su capacidad de adaptación a cambios de la cantidad de elementos

almacenados vemos las diferencias:

- Estructuras Estáticas:
o Rigidez: Debido a su naturaleza fija, las operaciones que requieren cambios en
el tamaño de la estructura (como inserciones y eliminaciones en un arreglo)
suelen ser ineficientes.
- Estructuras Dinámicas:
o Flexibilidad: Estas estructuras son flexibles en términos de tamaño. Pueden
crecer o encoger según las necesidades del programa. Sin embargo, esta
adaptabilidad viene con el costo de un mayor consumo de memoria debido al
uso de punteros o referencias adicionales.

Ten en cuenta
La diferencia fundamental entre estructuras estáticas y dinámicas se basa
en cómo gestionan y utilizan la memoria. Las estructuras estáticas son fijas
y utilizan bloques de memoria contigua, mientras que las estructuras
dinámicas son adaptables y utilizan punteros o referencias para conectar
sus elementos, que pueden estar dispersos en la memoria.

[Link]
© Universidad Alfonso X el Sabio 11
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

3.1.3. Tipos de TDAs

Veamos algunas de las EEDD más comunes:

- Arreglos (Arrays): Son colecciones contiguas de elementos, generalmente del mismo

tipo. Cada elemento se accede por un índice o posición.
- Listas Enlazadas: Son colecciones de elementos denominados nodos, donde cada nodo
apunta al siguiente en la lista. Pueden ser simples (solo apuntan hacia adelante) o
doblemente enlazadas (apuntan hacia adelante y atrás), e, incluso, circulares (el último
y el primer elemento están enlazados).
- Pilas (Stacks): Implementaciones basadas en el principio LIFO (último en entrar,
primero en salir). Se pueden implementar con arreglos o listas enlazadas.
- Colas (Queues): Basadas en el principio FIFO (primero en entrar, primero en salir). Al
igual que las pilas, se pueden implementar con arreglos o listas enlazadas.
- Tablas Hash: Permiten el almacenamiento y acceso rápido a datos basados en una
clave. Utilizan una función hash para determinar dónde almacenar cada elemento.
- Árboles: Estructuras jerárquicas que consisten en nodos conectados de manera que
forman una jerarquía. Los tipos específicos incluyen:
- Árboles Binarios: Cada nodo tiene hasta dos hijos.
o Árboles Binarios de Búsqueda (BST): Un árbol binario ordenado donde cada
nodo tiene un valor mayor que todos los nodos en su subárbol izquierdo y
menor que todos los nodos en su subárbol derecho.
o Árboles AVL, Árboles Rojo-Negro: Son BST equilibrados, donde se asegura que
el árbol permanezca aproximadamente balanceado para garantizar tiempos de
acceso, búsqueda e inserción eficientes.
o Árboles B: Son árboles de búsqueda que pueden tener más de dos hijos y se
utilizan principalmente en sistemas de almacenamiento.
- Grafos: Colecciones de nodos y aristas (conexiones) que pueden ser dirigidas o no
dirigidas. Se pueden representar usando listas de adyacencia, matrices de adyacencia,
entre otros.
- Colas de Prioridad: Estructuras que mantienen los elementos en un orden según su
prioridad. Una implementación común es el montículo (heap)
- Conjuntos (Sets): Colecciones de elementos sin orden específico y sin duplicados.
Pueden implementarse utilizando tablas hash, árboles o listas.
- Matrices: Arreglos bidimensionales que representan datos en filas y columnas.
Estas son solo algunas de las estructuras de datos principales que se utilizan en ciencias de la
computación y programación. La elección de una estructura de datos adecuada puede variar
según el problema específico que estés tratando de resolver y las operaciones que necesites
realizar con más frecuencia.

[Link]
© Universidad Alfonso X el Sabio 12
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

3.3. Listas enlazadas

En la sección anterior veíamos que las listas enlazadas son colecciones de elementos
denominados nodos, donde cada nodo apunta al siguiente en la lista. Y que estas pueden ser
simples (solo apuntan hacia adelante) o doblemente enlazadas (apuntan hacia adelante y atrás).

Cada nodo tiene dos partes principales:

- Dato: Contiene el valor del elemento. Este puede ser de cualquier tipo de dato admitido
por el lenguaje - básico o complejo -
- Referencia o Enlace: Apunta al siguiente nodo de la lista

El primer nodo de la lista se llama cabeza (head) y el último nodo apunta a null (None, en
Python), indicando el final de la lista. En el caso de listas circulares, el último nodo apuntará a la
cabeza, en lugar de a null.

Existen diversos tres tipos de listas enlazadas:

- Lista Enlazada Simple: Cada nodo apunta al siguiente nodo en la lista.

- Lista Enlazada Doble: Cada nodo tiene dos enlaces: uno apunta al siguiente nodo y otro
al anterior. Esto facilita el recorrido en ambas direcciones.

[Link]
© Universidad Alfonso X el Sabio 13
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

- Lista Enlazada Circular: El último nodo de la lista apunta de nuevo al primer nodo en
lugar de tener un enlace null.

3.3.1 Ventajas y desventajas

Ventajas de las Listas Enlazadas Desventajas de las Listas Enlazadas

Dinamismo: pueden crecer o encoger Acceso Secuencial: no hay acceso directo a los
fácilmente. elementos, se debe recorrer desde el inicio.
Inserción y eliminación eficientes Mayor Consumo de Memoria: se necesita
espacio adicional para almacenar
enlaces/pointers.
Uso de memoria según necesidad: no hay No hay soporte para acceso por índice, como
espacio desperdiciado. en los arreglos.
Flexibilidad: se pueden crear variantes como Mayor complejidad en el código al manejar
listas doblemente enlazadas o circulares. enlaces y casos especiales ([Link]., inserciones al
inicio).

Las listas enlazadas son estructuras dinámicas que son especialmente útiles cuando no sabes
cuántos elementos tendrás de antemano o cuando deseas realizar muchas inserciones y
eliminaciones. Sin embargo, su acceso secuencial y el uso adicional de memoria para enlaces
son desventajas a considerar en comparación con otras estructuras como los arreglos.

3.3.2 Operaciones comunes

Las operaciones comunes a todos los tipos de listas enlazadas son:

- Inserción: Puedes añadir un nodo al inicio, al final o en medio de la lista.

- Eliminación: Puedes quitar un nodo de la lista.
- Búsqueda: Puedes buscar un nodo en la lista por su valor.
- Recorrido: Puedes pasar por todos los nodos de la lista, generalmente comenzando por
la cabeza.

[Link]
© Universidad Alfonso X el Sabio 14
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

- Inversión: Puedes invertir el orden de los nodos en la lista.

3.3.3 Implementación de una lista enlazada en Python

Veamos una implementación sencilla de una lista enlazada escrita en Python. Para ello
declararemos dos clases correspondientes al Nodo y a la propia Lista Enlazada que contendrá
los métodos necesarios para su correcto uso.

Recordemos la clase `Nodo`:

class Nodo:
def __init__(self, valor):
[Link] = valor
[Link] = None

# Ejemplo de uso
nodo1 = Nodo(10)
nodo2 = Nodo(20)

[Link] = nodo2

print([Link]) # Imprimirá 10
print([Link]) # Imprimirá 20

Podemos observar cómo se declaran las dos partes del nodo, el dato y el enlace al elemento
siguiente de la lista. Fíjate que este enlace se crea vacío durante la instanciación del nodo, esto
es por que será la clase ListaEnlazada quien le de valor al incorporarlo a esta.

A continuación vemos la clase `ListaEnlazada`, pero veámosla por partes:

Declaramos la lista estableciendo la cabeza o punto de entrada a esta en el constructor:

class ListaEnlazada:
def __init__(self):
[Link] = None

[Link] Insercción

[Link]
© Universidad Alfonso X el Sabio 15
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

En el caso de la inserción, primero comprueba si la lista está vacía. Si lo está, simplemente coloca
el nuevo nodo en la cabeza de la lista. Si no lo está, navega hasta el final de la lista y coloca el
nuevo nodo allí.

1. Inicio del proceso

2. Crear un nuevo nodo usando el dato proporcionado.
3. Verificar si la lista está vacía (es decir, si la cabeza de la lista no apunta a ningún nodo).
4. Si la lista está vacía:
a. Hacemos que la cabeza de la lista apunte al nuevo nodo.
b. Terminamos el proceso.
5. Si la lista no está vacía:
a. Establecemos un nodo temporal (llamémosle "nodo actual") para comenzar en
la cabeza de la lista. Este nodo nos ayudará a navegar hasta el final.
b. Mientras el "nodo actual" tenga un nodo siguiente (es decir, mientras no
estemos en el último nodo de la lista):
i. Movemos el "nodo actual" al siguiente nodo en la lista. Básicamente,
avanzamos en
c. Una vez que hayamos llegado al final de la lista (cuando el "nodo actual" no
tenga un nodo siguiente):
i. Hacemos que el siguiente del "nodo actual" apunte al nuevo nodo.
6. Fin del proceso.

Veámoslo en formato de flujograma o diagrama de flujo:

[Link]
© Universidad Alfonso X el Sabio 16
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Ilustración. Flujograma de inserción de nuevo nodo al final de la lista. Fuente: elaboración propia

A continuación el código fuente en Python:

[Link]
© Universidad Alfonso X el Sabio 17
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

# Inserción al final
def insertar(self, dato):
nuevo_nodo = Nodo(dato)
if not [Link]:
[Link] = nuevo_nodo
return
ultimo_nodo = [Link]
while ultimo_nodo.siguiente:
ultimo_nodo = ultimo_nodo.siguiente
ultimo_nodo.siguiente = nuevo_nodo

[Link]. Eliminar (por valor)

En este caso eliminamos un nodo con un valor específico. Para ello debemos encontrarlo y
posteriormente eliminarlo. Veamos los pasos:

1. Inicio del proceso.

2. Verificamos si la lista está vacía.
a. Si la lista está vacía, no hay nada que eliminar. Termina el proceso.
3. Verificamos, si el nodo que está en la cabeza de la lista (primer nodo) tiene el valor que
deseamos eliminar.
a. Si es así, hacemos que la cabeza de la lista apunte al segundo nodo (es decir, el
nodo siguiente al actual). De esta manera, hemos eliminado el primer nodo de
la lista. Termina el proceso.
4. Si no hemos eliminado el nodo en el paso anterior, preparamos dos nodos temporales:
a. Un "nodo actual" que empiece desde la cabeza de la lista.
b. Un "nodo previo" que inicialmente será `None`.
5. Recorremos la lista buscando el valor a eliminar:
a. Mientras el "nodo actual" no sea `None` y no tenga el valor que buscamos:
i. Movemos el "nodo previo" al "nodo actual".
ii. Movemos el "nodo actual" al siguiente nodo en la lista.
6. Al final de la iteración anterior, una de estas dos cosas es cierta:

[Link]
© Universidad Alfonso X el Sabio 18
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

a. El "nodo actual" es `None`, lo que significa que hemos recorrido toda la lista y
el valor no se encuentra en ella. En ese caso, no hay nada más que hacer.
b. Hemos encontrado el nodo con el valor que buscas. El "nodo actual" apunta a
ese nodo y el "nodo previo" apunta al nodo justo antes del que deseas eliminar.
7. Si hemos encontrado el nodo a eliminar:
a. Hacemos que el "nodo siguiente" del "nodo previo" apunte al nodo que viene
después del "nodo actual". De esta manera, hemos "saltado" sobre el "nodo
actual", eliminándolo de la lista.
8. Fin del proceso.

Veámoslo en formato de flujograma o diagrama de flujo:

[Link]
© Universidad Alfonso X el Sabio 19
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Ilustración. Flujograma de eliminación de nodo. Fuente: elaboración propia

A continuación el código fuente en Python:

[Link]
© Universidad Alfonso X el Sabio 20
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

# Eliminación por valor

def eliminar(self, dato):
nodo_actual = [Link]
if nodo_actual and nodo_actual.dato == dato:
[Link] = nodo_actual.siguiente
nodo_actual = None
return
previo = None
while nodo_actual and nodo_actual.dato != dato:
previo = nodo_actual
nodo_actual = nodo_actual.siguiente

if nodo_actual is None:
return

[Link] = nodo_actual.siguiente
nodo_actual = None

Ten en cuenta que, dependiendo del lenguaje de programación que estés utilizando - es el caso
de C, C++ o C#, entre otros-, puede ser necesario que liberes la memoria del nodo eliminado de
forma manual. En Python, gracias al recolector de basura, el nodo se eliminará automáticamente
cuando no haya referencias a él.

1.3.3. 3. Buscar (por valor)

En este caso buscamos un nodo con un valor específico. Para ello debemos recorrer la lista nodo
por nodo, desde el principio hasta el final, buscando un nodo con un valor específico. Veamos
los pasos:

1. Inicio del proceso.

2. Verifica si la lista está vacía.
a. Si la lista está vacía, informa que el valor no está en la lista y termina el proceso.
3. Si la lista no está vacía:
a. Establece un "nodo actual" para comenzar en la cabeza de la lista. Este nodo te
ayudará a navegar por la lista.
b. Establece una variable "posición" a 0, que nos ayudará a identificar en qué
posición de la lista se encuentra el nodo que estamos buscando.

[Link]
© Universidad Alfonso X el Sabio 21
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

4. Recorre la lista buscando el valor:

a. Mientras el "nodo actual" no sea None:
i. Si el "nodo actual" tiene el valor que buscas:
1. Informa que el valor se encontró en la "posición" y termina el
proceso.
ii. Si el "nodo actual" no tiene el valor que buscas:
1. Mueve el "nodo actual" al siguiente nodo en la lista.
2. Incrementa el valor de "posición" en 1.
5. Si has recorrido toda la lista y no has encontrado el valor:
a. Informa que el valor no se encuentra en la lista.
6. Fin del proceso.

Veámoslo en formato de flujograma:

[Link]
© Universidad Alfonso X el Sabio 22
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Ilustración. Flujograma de búsqueda de nodo por valor. Fuente: elaboración propia

A continuación el código fuente en Python:

[Link]
© Universidad Alfonso X el Sabio 23
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

# Búsqueda
def buscar(self, dato):
nodo_actual = [Link]
while nodo_actual:
if nodo_actual.dato == dato:
return nodo_actual
nodo_actual = nodo_actual.siguiente
return False

Ten en cuenta
Es un proceso sencillo, pero es una operación de búsqueda lineal, lo que
significa que, en el peor de los casos, tendríamos que recorrer toda la lista
para determinar si un valor está presente o no.

1.3.3. 4. Actualizar (por posición)

En este caso buscamos un nodo en una posición específica para modificar sus datos. Para ello
debemos recorrer la lista nodo por nodo, desde el principio hasta la posición buscada y
modificamos la carga del nodo. Veamos los pasos:

1. Inicio del proceso

2. Comprobamos si la lista está vacía.
a. Si la lista lo está, anunciamos que la posición dada no es válida y finaliza el
procedimiento.
3. Si la lista no se halla vacía:
a. Establecemos un "nodo actual" para comenzar en la cabeza de la lista y una
variable "posición actual" en 0.
4. Recorremos la lista buscando la posición:
a. Mientras el "nodo actual" no sea `None`:
i. Si la "posición actual" coincide con la posición dada:
1. Realizamos la actualización del valor en el "nodo actual".
2. Informamos que la actualización ha sido exitosa y finaliza el
proceso.

[Link]
© Universidad Alfonso X el Sabio 24
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

ii. En caso contrario:

1. Desplazamos el "nodo actual" al siguiente nodo en la lista.
2. Incrementamos el valor de "posición actual".
5. Si hemos atravesado toda la lista y no hemos encontrado la posición:
a. Informamos que la posición dada no es válida.
6. Fin del proceso.

[Link]
© Universidad Alfonso X el Sabio 25
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Veámoslo en formato de flujograma:

Ilustración. Flujograma de actualización de nodo por posición. Fuente: elaboración propia

[Link]
© Universidad Alfonso X el Sabio 26
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

A continuación el código fuente en Python:

# Actualización por posición

def actualizar(self, posicion, nuevo_dato):
nodo_actual = [Link]
indice = 0
while nodo_actual:
if indice == posicion:
nodo_actual.dato = nuevo_dato
return
nodo_actual = nodo_actual.siguiente
indice += 1

1.3.3. 5. Recorrer
En este caso vamos a recorrer todos los nodos de la lista. Para ello comenzamos desde el primer
elemento y avanzamos uno a uno hasta el final. Veamos los pasos:

1. Inicio.
2. Verificamos si la lista está vacía.
a. Si la lista está vacía, informamos que no hay elementos para recorrer y
terminamos el proceso.
3. Si la lista no está vacía:
a. Establecemos un "nodo actual" para empezar en la cabeza de la lista.
4. Comenzamos a recorrer la lista:
a. Mientras el "nodo actual" no sea `None`:
i. Procesamos (o mostramos) el valor del "nodo actual".
ii. Movemos el "nodo actual" al siguiente nodo en la lista.
5. Fin del proceso.

Veámoslo en formato de flujograma:

[Link]
© Universidad Alfonso X el Sabio 27
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Ilustración. Flujograma de recorrido de la lista. Fuente: elaboración propia

A continuación el código fuente en Python:

[Link]
© Universidad Alfonso X el Sabio 28
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

# Travesía o recorrido
def recorrer(self):
nodos = []
nodo_actual = [Link]
while nodo_actual:
print(nodo_actual.dato)
[Link](nodo_actual.dato)
nodo_actual = nodo_actual.siguiente
return nodos

En este fragmento de código, no solo recorremos la lista, si no que imprimimos el dato de cada
nodo y añadimos cada nodo a una colección de nodos que devolveremos al finalizer el recorrido.

1.3.3. 6. Ordenar
Veamos el proceso de ordenar los elementos de una lista enlazada bajo un criterio específico,
ya sea ascendente o descendente. Hay varios algoritmos para ordenar una lista -los
trabajaremos en temas posteriores-, pero explicaremos un enfoque básico: el algoritmo de
burbuja adaptado para listas enlazadas. Aunque no es el más eficiente, ilustra bien el concepto.
En este ejemplo, asumimos que los datos son de tipo numérico para simplificar el código.

1. Inicio del proceso.

2. Verificamos si la lista está vacía o tiene un solo elemento.
a. Si es así, informamos que la lista ya está ordenada y finalizamos el proceso.
3. Iniciamos la ordenación:
a. Establecemos un "nodo actual" en la cabeza de la lista.
b. Mientras el "nodo actual" no sea `None`:
i. Establecemos un "nodo siguiente" como el siguiente del "nodo actual".
ii. Mientras el "nodo siguiente" no sea `None`:
1. Si el valor del "nodo actual" es mayor que el valor del "nodo
siguiente" (para orden ascendente), intercambiamos sus
valores.
2. Movemos el "nodo siguiente" al siguiente nodo en la lista.
iii. Movemos el "nodo actual" al siguiente nodo en la lista y repetimos el
proceso.
4. Una vez que hemos ordenado toda la lista, finalizamos el proceso.

[Link]
© Universidad Alfonso X el Sabio 29
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Veámoslo en formato de flujograma:

Ilustración. Flujograma de ordenación mediante algoritmo de burbuja. Fuente: elaboración propia

[Link]
© Universidad Alfonso X el Sabio 30
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

A continuación el código fuente en Python:

# Ordenar (asumiendo que son números para simplificar)

def ordenar(self):
if not [Link]:
return

nodo_actual = [Link]
while nodo_actual:
siguiente = nodo_actual.siguiente
while siguiente:
if nodo_actual.dato > [Link]:
nodo_actual.dato, [Link] = [Link], nodo_actual.dato
siguiente = [Link]
nodo_actual = nodo_actual.siguiente

1.3.3. 7. Acceder a nodo por posición

El acceso por posición implica obtener el nodo que se encuentra en una posición específica de
la lista enlazada. Aquí están los pasos para realizar esta operación. Veamos los pasos

1. Inicio
2. Comprobamos si la lista está vacía.
a. Si la lista está vacía, informamos que la posición no es válida y terminamos el
proceso.
3. Establecemos un "nodo actual" en la cabeza de la lista y una variable "contador" en 0.
4. Recorremos la lista:
a. Mientras el "nodo actual" no sea `None`:
i. Si "contador" es igual a la posición deseada:
1. Devolvemos el dato del "nodo actual" y terminamos el proceso.
ii. Si no, movemos el "nodo actual" al siguiente nodo y incrementamos el
"contador" en 1.
5. Si se ha recorrido toda la lista y no se ha encontrado la posición, informamos que la
posición no es válida.
6. Fin

Veámoslo en formato de flujograma:

[Link]
© Universidad Alfonso X el Sabio 31
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Ilustración. Flujograma de acceso a nodo por posición. Fuente: elaboración propia

A continuación el código fuente en Python:

[Link]
© Universidad Alfonso X el Sabio 32
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

# Acceso por posición

def acceso(self, posicion):
nodo_actual = [Link]
indice = 0
while nodo_actual:
if indice == posicion:
return nodo_actual.dato
nodo_actual = nodo_actual.siguiente
indice += 1
return None

1.3.3. 8. Longitud o tamaño de la lista

En multitude de ocasiones necesitamos conocer la cantidad de nodos que temenos
almacenados en nuestra lista, por lo que podemos optar por dos sistemas: mediante recorrido
o mediante atributo de la clase ‘ListaEnlazada’.

El sistema de recorrido consiste en incorporar un contador al método de ‘recorrer’, de modo

que cada vez que encntremos un nuevo nodo, incrementaremos el valor del contador, y
devolveremos su valor al finalizar el recorrido.

Y el otro sistema consiste en incorporar un atributo a nuestra clase ListaEnlazada que nos
permita mantener un contador de elementos de modo que este se actualice cada vez que
llevemos a cabo una operación de insercción o eliminación de nodos.

Desarrolla
Te dejo la doble tarea de:
- Desarrollar un método que recorra la lista contando los elementos
encontrados y devuelva el valor del recuento.
- Incorporar el atributo de clase ‘longitud’ a la clase ‘ListaEnlazada’ y
modificar los métodos de insertar y eliminar para actualizar ese
atributo según convenga.

1.3.3. 9. Verificar si la lista está vacía

Terminamos con el método más sencillo de todos, el de verificación si la lista está vacía. Su
principal objetivo es determinar si la lista contiene algún nodo o no. Para ello, simplemente se
verifica si el nodo cabeza (el primer nodo de la lista) es `None` (o null, en algunos lenguajes). Si
es `None`, la lista está vacía; de lo contrario, no lo está.

[Link]
© Universidad Alfonso X el Sabio 33
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

No necesitas el diagrama de flujo de este método ¿verdad? Pero, por si las dudas, te dejo el
código fuente:

# Verificación de vacío
def esta_vacia(self):
return [Link] is None

3.4. Pilas

Pongamos otro ejemplo, la de la pila de platos en la cocina ¿cómo funciona? Básicamente

tenemos un plato encima de otro, de modo que cuando estamos recogiendo el lavavajillas los
vamos dejando sobre los que ya están. Y cuando necesitamos uno, tomamos el de más arriba.

A esto lo definimos como “Last-In, First-Out” – útimo en llegar, primero en salir, en español – lo
que venimos llamando LIFO.

Ilustración 1. Título. Pila. Fuente: User:Boivie, Public domain, via Wikimedia Commons

[Link]
© Universidad Alfonso X el Sabio 34
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Principales características:
 Ordenamiento LIFO: Los elementos se eliminan en el orden inverso en el que se
agregaron. El último elemento que se agrega es el primero en ser eliminado. Orden
inverso.

 Estructura lineal: Los elementos se almacenan en una estructura lineal,

generalmente implementada utilizando un array o una lista enlazada.

 Operaciones básicas:

 push: Agregar un elemento a la parte superior de la pila.

 pop: Eliminar y retornar el elemento en la parte superior de la pila.

 top (o peek): Obtener el elemento en la parte superior de la pila sin eliminarlo.

 isEmpty: Verificar si la pila está vacía.

Habitualmente utilizamos las pilas en situaciones donde es importante recordar el orden de
llegada de los elementos, como en la gestión de llamadas de funciones en una pila de ejecución
de un programa o en el historial del navegador web.

Un caso especial es el de las "colas de prioridad", donde los elementos tienen asignadas
prioridades y se eliminan en función de su prioridad en lugar de su orden de llegada. Y, en caso
de que tengan la misma prioridad, se decide por su orden de llegada.

Implementación
Aquí tienes el código fuente de implementación de una pila o stack:

class Stack:
def __init__(self):
[Link] = []

def esta_vacia(self):
return len([Link]) == 0

def push(self, elemento):

[Link](elemento)

def pop(self):
if not self.esta_vacia():
return [Link]()
else:
raise IndexError("La pila está vacía")

[Link]
© Universidad Alfonso X el Sabio 35
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

def peek(self):
if not self.esta_vacia():
return [Link][-1]
else:
raise IndexError("La pila está vacía")

def tamano(self):
return len([Link])

# Ejemplo de uso
mi_pila = Stack()

mi_pila.push(1)
mi_pila.push(2)
mi_pila.push(3)

print("Elementos en la pila:", mi_pila.items) # Imprime [1, 2, 3]

ultimo_elemento = mi_pila.pop()
print("Último elemento eliminado:", ultimo_elemento) # Imprime 3

print("Elementos en la pila después de eliminar:", mi_pila.items) # Imprime [1, 2]

print("Tamaño de la pila:", mi_pila.tamano()) # Imprime 2

[Link]
© Universidad Alfonso X el Sabio 36
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

3.5. Listas enlazadas

Recuerda las fiestas del pueblo de este verano, cuando la orquesta empieza a tocar Paquito el
chocolatero, y todo el mundo se coloca en fila y le da la mano a la persona que tiene delante y
a la que tiene detrás, cada quién sabe quiénes son sus compañeros más inmediatos ya que está
enlazado a ellos. Pues eso es una lista enlazada o linked list.

Sus principales características son:

 Estructura de Nodos: En una lista enlazada, los elementos se almacenan en nodos.

Cada nodo consta de dos partes:

 Dato o Valor: Esta parte almacena el elemento de datos en sí, como un número, una
cadena o cualquier otro tipo de valor.

 Referencia o Enlace: Este componente contiene una referencia al siguiente nodo en

la lista. En algunas listas enlazadas, también puede haber una referencia al nodo
anterior en el caso de listas doblemente enlazadas.

Valor Ref.

class Nodo:
def __init__(self, valor):
[Link] = valor
[Link] = None

class ListaEnlazada:
def __init__(self):
[Link] = None

 Acceso Secuencial: Para acceder a un elemento específico en una lista enlazada,

generalmente debes recorrer la lista desde el inicio (nodo principal o cabeza) hasta
el nodo deseado. Esto implica un acceso secuencial en lugar de acceso directo, como
en los arrays.

 Inserciones y Eliminaciones Eficientes: Las listas enlazadas son especialmente

eficientes en la inserción y eliminación de elementos en cualquier posición, siempre
que tengas una referencia al nodo en esa posición.

[Link]
© Universidad Alfonso X el Sabio 37
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

 Uso de Memoria: Cada nodo en una lista enlazada requiere memoria adicional para
almacenar la referencia al siguiente nodo. Esto puede hacer que las listas enlazadas
consuman más memoria que estructuras de datos similares, como arrays, que
almacenan elementos de manera contigua.
Podemos encontrar, principalmente, tres tipos de listas enlazadas:

 listas enlazadas simples: con referencias únicamente al nodo siguiente

 listas enlazadas dobles: con referencias al nodo siguiente y al nodo anterior

 listas enlazadas circulares: donde el último nodo apunta al primero, formando un

bucle.

Habitualmente, utilizamos las listas enlazadas cuando necesitamos insertar o eliminar

elementos frecuentemente en cualquier posición. También se utilizan en la implementación de
otras estructuras de datos, como pilas, colas y árboles.

Operaciones sobre las listas enlazadas

Las operaciones que podemos y solemos realizar sobre las listas enlazadas son las siguientes:

 Inserción al principio, al final, en una posición intermedia específica.

 Eliminación al principio, al final, de una posición intermedia específica.

 Búsqueda de un elemento específico

 Obtención de la longitud o cantidad de nodos

 Acceso a un elemento de una posición determinada

 Inversión del orden de los nodos de la lista

 Concatenación de dos listas formando una de mayor tamaño

Inserción al principio

Para ello llevaremos a cabo los siguientes pasos:

1. Creamos el nuevo nodo.

2. Tomamos primer nodo del enlace de la cabeza y lo enlazamos desde el nuevo nodo
3. Cambiamos el enlace de la cabeza al nuevo nodo

[Link]
© Universidad Alfonso X el Sabio 38
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Es importante que sigamos el orden de los pasos anteriores, ya que en caso contrario
perderíamos información sobre los elementos.

def insertar_al_principio(self, dato):

nuevo_nodo = Nodo(dato)
nuevo_nodo.siguiente = [Link]
[Link] = nuevo_nodo

Inserción al final

Para ello llevaremos a cabo los siguientes pasos:

1) Creamos el nuevo nodo.

2) Comprobamos si la lista está vacía. En caso de que esté vacía insertamos al principio
de la lista. En caso de que no esté vacía seguimos al paso 3.
3) Recorremos la lista hasta que encontramos el último nodo
4) Conectamos el último nodo al nuevo nodo
Es importante que sigamos el orden de los pasos anteriores, ya que en caso contrario
perderíamos información sobre los elementos.

def insertar_al_final(self, dato):

nuevo_nodo = Nodo(dato)
if self.esta_vacia():
[Link] = nuevo_nodo
else:
actual = [Link]
while [Link]:
actual = [Link]
[Link] = nuevo_nodo

Inserción en una posición concreta

Para ello llevaremos a cabo los siguientes pasos:

1) Creamos el nuevo nodo.

[Link]
© Universidad Alfonso X el Sabio 39
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

2) Comprobamos si la lista está vacía. En caso de que esté vacía insertamos al principio
de la lista. En caso de que no esté vacía seguimos al paso 3.
3) Recorremos la lista hasta que encontramos el último nodo
4) Conectamos el último nodo al nuevo nodo

def insertar_en_posicion(self, dato, posicion):

nuevo_nodo = Nodo(dato)
if posicion == 0:
nuevo_nodo.siguiente = [Link]
[Link] = nuevo_nodo
else:
actual = [Link]
for _ in range(posicion - 1):
if actual is None:
raise IndexError("Posición fuera de rango")
actual = [Link]
nuevo_nodo.siguiente = [Link]
[Link] = nuevo_nodo

La eliminación de un nodo en una lista enlazada puede involucrar varios casos, dependiendo de
dónde se encuentra el nodo que se va a eliminar y cómo se relaciona con otros nodos en la lista.
Aquí están los casos más comunes de eliminación de un nodo en una lista enlazada:

Eliminar el primer nodo (cabeza)

Este caso implica eliminar el nodo que está al principio de la lista (la cabeza). Para realizar esta
eliminación, se actualiza la cabeza de la lista para que apunte al siguiente nodo en la lista. Es
importante verificar si la lista está vacía antes de intentar eliminar el primer nodo.

def eliminar_primero(self):
if [Link] is not None:
[Link] = [Link]

Eliminar el último nodo

[Link]
© Universidad Alfonso X el Sabio 40
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Para eliminar el último nodo de la lista, se debe recorrer la lista hasta llegar al penúltimo nodo
(el nodo anterior al último). Luego, se ajusta el puntero del penúltimo nodo para que apunte a
`None` o al nodo siguiente (dependiendo de cómo se implemente la lista enlazada), lo que
desconecta el último nodo.

def eliminar_ultimo(self):
if [Link] is None:
return

if [Link] is None:
[Link] = None
return

actual = [Link]
while [Link]:
actual = [Link]
[Link] = None

Eliminar un nodo en el medio de la lista (o por valor)

Cuando el nodo no es ni el primero ni el último, se deben ajustar los punteros del nodo anterior
al nodo que se va a eliminar y del nodo que se va a eliminar al siguiente nodo. Este proceso
desconecta el nodo que se va a eliminar de la lista y lo hace elegible para la recolección de
basura.

En caso de que se deba eliminar el nodo en base a su valor, se debe buscar el nodo que contiene
el valor que se desea eliminar. Una vez encontrado, se ajustan los punteros del nodo anterior al
nodo que se va a eliminar y del nodo que se va a eliminar al siguiente nodo.

def eliminar_por_valor(self, valor):

if [Link] is None:
return

if [Link] == valor:
[Link] = [Link]
return

actual = [Link]
while [Link]:
if [Link] == valor:

[Link]
© Universidad Alfonso X el Sabio 41
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

[Link] = [Link]
return
actual = [Link]

Recuerda que Python dispone de un sistema de recolección de basura automática (garbage

collection, en inglés) que se encarga de gestionar la memoria, eliminando objetos que ya no son
referenciados o utilizados por el programa.

Eliminar nodos duplicados

Otro caso un tanto más particular es cuando necesitamos eliminar todos los nodos que
contienen un valor duplicado en la lista. Esto significa que debemos recorrer la lista y, cuando
encontramos un nodo con el valor deseado, lo eliminamos de la misma manera que en los casos
anteriores.

Este proceso suele requerir un bucle para eliminar todas las ocurrencias del valor duplicado.

Eliminar todos los nodos

En caso de que necesitemos eliminar todos los nodos de la lista para dejarla vacía, podemos
hacer un bucle que recorra la lista y elimine cada nodo uno por uno.

La eliminación de nodos en una lista enlazada es una operación importante que debe
implementarse con cuidado para asegurarnos de que los punteros se actualicen correctamente
y que no se produzcan fugas de memoria. La implementación exacta de estos casos de
eliminación puede variar según la estructura de la lista enlazada y cómo se gestionen los
punteros o enlaces.

Dejo para ti la implementación de los métodos necesarios para estos dos últimos casos.

Búsqueda de un elemento o elementos con valores concretos

Tal y como hemos visto en casos previos, recorreremos la lista hasta encontrar el elemento o
elementos que cumplen las condiciones de búsqueda. Más adelante veremos cómo podemos
aprovechar los algoritmos de búsqueda para optimizar este proceso.

¿Cuál sería el código base para un método de búsqueda de elementos en una lista enlazada?

Obtención de la longitud o cantidad de nodos

[Link]
© Universidad Alfonso X el Sabio 42
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

En este punto podemos optar por dos soluciones, una es recorrer todos los elementos de la lista,
contando uno a uno. La otra opción es que incorporemos una propiedad a nuestra clase lista, en
la que llevemos el control de la cantidad de elementos que contiene. En este caso, recuerda que
debemos aumentar o disminuir su valor según el tipo de operación que hayamos realizado.

class ListaEnlazada:
def __init__(self):
[Link] = None
[Link] = 0 # Inicialmente, la lista está vacía
# ...

Acceso a un elemento de una posición determinada

En este caso, recorreremos los nodos mediante un bucle hasta que alcancemos la posición

[Link]
© Universidad Alfonso X el Sabio 43
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

def obtener_elemento(self, posicion):

if [Link] is None:
return None # La lista está vacía
actual = [Link]
indice = 0

while actual is not None:

if indice == posicion:
return [Link]
actual = [Link]
indice += 1

return None # La posición especificada no existe en la lista

Inversión del orden de los nodos de la lista

En múltiples ocasiones podemos encontrarnos la necesidad de invertir el orden de los nodos de
la lista: visualización de datos, procesamiento en orden inverso, implementación de una pila o
una cola, implementación de un sistema de histórico de modificaciones (deshacer-rehacer) e
incluso para la optimización de algoritmos.

El método invertir recorre la lista enlazada original y, en cada paso, invierte el puntero siguiente
del nodo actual para que apunte al nodo anterior (previo). De esta manera, los nodos se
reorganizan en orden inverso. Al final del bucle, la cabeza de la lista se establece como el último
nodo invertido (anterior cabeza).

def invertir(self):
previo = None # Nodo anterior
actual = [Link] # Nodo actual
while actual:
siguiente = [Link] # Guardar el siguiente nodo
[Link] = previo # Invertir el ptro. del nodo actual
previo = actual # Mover previo al nodo actual
actual = siguiente # Mover actual al siguiente nodo
[Link] = previo # La nueva cabeza será el último nodo invertido

[Link]
© Universidad Alfonso X el Sabio 44
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Concatenación de dos listas formando una de mayor tamaño

Concatenar listas enlazadas puede ser útil en diversas situaciones en las que desees combinar
dos listas en una sola. Como por ejemplo para fusionar datos de múltiples fuentes, segmentos
de lista o resultados de sublistas.

En este método tomamos otra lista enlazada como argumento y la concatenamos con la lista
actual. Si la lista actual está vacía, simplemente establecemos su cabeza como la cabeza de la
otra lista. Si la lista actual no está vacía, recorremos la lista actual hasta encontrar el último nodo
y conectamos su siguiente al principio de la otra lista.

def concatenar(self, otra_lista):

if [Link] is None:
[Link] = otra_lista.cabeza
else:
actual = [Link]
while [Link]:
actual = [Link]
[Link] = otra_lista.cabeza

Te invito a que revises el código que te he propuesto y lo optimices aplicando el

principio DRY (“Don’t Repeat Yourself”).

[Link]
© Universidad Alfonso X el Sabio 45
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Listas doblemente enlazadas

Este tipo de listas, también conocidas como "doubly linked list" en inglés, se comportan
prácticamente igual que las listas enlazadas vistas líneas arriba, la principal diferencia es que en
lugar de que cada nodo se enlace únicamente con el siguiente, se enlaza también con el nodo
anterior. Este sistema nos permite la navegación bidireccional de la lista. Esto nos permite
acceder a la lista desde cualquier nodo pudiendo recorrerla completamente. Además de que
nos facilita la inserción de nuevos nodos en cualquier punto de la lista.

Veamos la estructura del nodo

class NodoDoble:
def __init__(self, dato):
[Link] = dato
[Link] = None
[Link] = None

Te propongo un ejercicio, escribe el código de los siguientes métodos de una lista doblemente
enlazada:

def agregar_al_principio(self, dato):

def agregar_al_final(self, dato):
def insertar_en_posicion(self, dato, posicion):
def eliminar_al_principio(self):
def eliminar_al_final(self):
def eliminar_en_posicion(self, posicion):
def longitud(self):

[Link]
© Universidad Alfonso X el Sabio 46
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

3.6. Árboles

Imagina un árbol como el que puedes ver en la naturaleza, con un tronco y ramas que se dividen
en más ramas, y así sucesivamente. En el mundo de las estructuras de datos, un árbol es una
forma de organizar datos de manera jerárquica, donde cada elemento es un nodo.

Tipos de árboles
Dependiendo de la cantidad máxima de hijos por nodo y su comportamiento encontramos
distintos tipos de árboles

 Árbol N-ario: Un tipo de árbol en el que cada nodo puede tener hasta n nodos hijos.

 Árbol Binario: Un tipo de árbol en el que cada nodo tiene como máximo dos hijos,
uno izquierdo y otro derecho.

 Árbol Nulo o Vacío: Un de árbol que no tiene ningún nodo.

 Árbol de Búsqueda Binaria (BST): Un árbol binario en el que los valores están
organizados de manera que los valores menores se ubican en el subárbol izquierdo
y los valores mayores en el subárbol derecho.

 Árbol AVL: Un tipo de árbol de búsqueda binaria equilibrado donde la diferencia de

alturas entre los subárboles izquierdo y derecho de cualquier nodo es, como
máximo, uno.

 Árbol Trie: Un árbol especializado en estructuras de datos que se utiliza

comúnmente para almacenar y buscar cadenas de caracteres.

 Árbol de Decisión: Un tipo de árbol utilizado en algoritmos de aprendizaje

automático para la toma de decisiones basada en reglas y condiciones.

 Árbol de Expansión Mínima (Minimum Spanning Tree): Un subconjunto de un grafo

conectado que conecta todos los vértices con el mínimo costo posible.

 Árbol de Sintaxis Abstracta (AST): Un árbol utilizado en la representación de la

estructura sintáctica de un programa de computadora.

En cuanto a los nodos – también conocidos como vértices - de un árbol, cada nodo puede tener
cero o más "hijos". Estos hijos son otros nodos conectados a él. Entre los nodos tenemos
diferentes categorías:

 Nodo Raíz: es el nodo superior en la jerarquía del árbol. Es el punto de partida desde
el cual se ramifican todos los demás nodos. En un árbol, solo hay un nodo raíz.

[Link]
© Universidad Alfonso X el Sabio 47
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

 Nodo Padre: todo nodo (excepto el nodo raíz) tiene un nodo padre, que es el nodo
directamente superior a él. El nodo padre tiene una referencia a cada uno de sus
nodos hijos

 Nodo Hijo: son los nodos que están conectados directamente a un nodo padre.
Pueden ser cero o más, dependiendo del tipo de árbol.

 Nodo Hoja: son los nodos que no tienen hijos. Estos son los nodos finales en una
rama del árbol.

 Nodo Interno: los nodos internos son aquellos que tienen uno o más nodos hijos.
Están en algún lugar entre el nodo raíz y los nodos hoja.

Ilustración 2 Tipos de nodos de un árbol. Fuente: elaboración propia

Antes de continuar, vamos a hacer un repaso de otros conceptos importantes acerca de los
árboles:

 Altura: La longitud del camino más largo desde un nodo hasta un nodo hoja en un
árbol.

 Altura del árbol: Es la longitud del camino desde el nodo raíz hasta el nodo hoja más
lejano.

 Nivel: La distancia entre un nodo y el nodo raíz. El nodo raíz tiene nivel 0.

 Subárbol: Un árbol que se forma tomando un nodo y todos sus descendientes.

[Link]
© Universidad Alfonso X el Sabio 48
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

 Arista: La relación entre un par de nodos, solemos pintarlas con una flecha (o línea)

 Bosque: Un conjugo de árboles no conectados entre sí.

 Hermanos: Son aquellos nodos que tienen el mismo padre.

 Descendientes de un nodo, son todos aquellos nodos que forman parte del subárbol
cuya raíz es ese nodo (los hijos, los nietos, bisnietos …)

 Ancestros de un nodo son todos aquellos nodos que se encuentran en el camino

entre él y la raíz.

 Grado de un nodo es la cantidad de hijos que tiene

 Grado de un árbol: es el número máximo de los grados de todos los nodos

 Ancestros de un nodo son todos aquellos nodos que se encuentran en el camino

entre él y la raíz.

Bien, ahora que ya tenemos claros estos conceptos, vamos a por el código. Veamos la
implementación de un árbol N-ario.

Ilustración 3 Árbol ternario (3-ario). Fuente: elaboración propia

Analicemos el árbol de la ilustración.

[Link]
© Universidad Alfonso X el Sabio 49
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

 Tipo de árbol: Es un árbol jerárquico donde "Raíz" es el nodo raíz del árbol y tiene
tres hijos directos: "P1," "P2," y "P3."

 Niveles: El árbol tiene cuatro niveles en total, contando desde la raíz ("Raíz") hasta
los nodos más profundos.

 Número de hijos: Los nodos pueden tener entre 0 y 2 hijos, lo que representa la
variabilidad en la cantidad de descendientes que un nodo puede tener.
A continuación, vamos a analizar los nodos individuales:

 Raíz: Es el nodo raíz del árbol y no tiene un padre. Tiene tres hijos directos: "P1,"
"P2," y "P3."

 P1: Es un nodo intermedio con tres hijos: "H1.1," "P1.2," y "H1.3." Muestra que un
nodo intermedio puede tener múltiples descendientes, incluyendo nodos hoja y
nodos intermedios.

 P2: Es un nodo intermedio con un solo hijo, "H2.1." Representa un caso donde un
nodo intermedio tiene un único descendiente.

 P3: Es un nodo intermedio con dos hijos: "P3.1" y "H3.2." Esto muestra cómo un
nodo intermedio puede tener 0 o más hijos, incluyendo otros nodos intermedios y
nodos hoja.

 H1.1: Es una hoja porque no tiene hijos.

 H1.3: Es una hoja porque no tiene hijos.

 H2.1: Es una hoja porque no tiene hijos. Esto demuestra que un nodo puede ser una
hoja directamente bajo un nodo intermedio.

 P1.2: Es un nodo intermedio con dos hijos: "H1.2.1" y "H1.2.2." Representa un caso
de un nodo intermedio con múltiples descendientes.

 P3.1: Es un nodo intermedio con dos hijos: "H3.1.1" y "H3.1.2."

 H1.2.1: Es una hoja porque no tiene hijos.

 H1.2.2: Es una hoja porque no tiene hijos.

 H3.1.1: Es una hoja porque no tiene hijos.

 H3.1.2: Es una hoja porque no tiene hijos.

Operaciones sobre árboles

[Link]
© Universidad Alfonso X el Sabio 50
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Definamos, en primer lugar, el nodo de un árbol N-Ario, la clase del árbol y su constructor:

class NodoArbolNArio:
def __init__(self, valor):
[Link] = valor
[Link] = []

class ArbolNArio:
def __init__(self, raiz=None):
[Link] = raiz

Veamos qué operaciones podemos implementar sobre los árboles:

 Añadir un elemento: incorpora un nodo al árbol. Indicaremos la posición o

permitiremos que el propio árbol lo coloque en su sitio, en caso de que sea un árbol
ordenado.

def agregar_elemento(self, valor, padre=None):

nuevo_nodo = NodoArbolNArio(valor)
if not padre:
if not [Link]:
[Link] = nuevo_nodo
else:
[Link](nuevo_nodo)
else:
[Link](nuevo_nodo)

 Eliminar un elemento: retira un elemento del árbol

def eliminar_elemento(self, valor):

if [Link]:
[Link] = [n for n in [Link] if [Link] != valor]
for hijo in [Link]:
self._eliminar_recursivo(hijo, valor)

def _eliminar_recursivo(self, nodo_actual, valor):

nodo_actual.hijos = [n for n in nodo_actual.hijos if [Link] != valor]
for hijo in nodo_actual.hijos:
self._eliminar_recursivo(hijo, valor)

[Link]
© Universidad Alfonso X el Sabio 51
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

 Podar: borrar una sección entera de un árbol, es decir, un subárbol.

def podar_subarbol(self, valor):

if [Link]:
[Link] = [n for n in [Link] if [Link] != valor]
for hijo in [Link]:
self._podar_recursivo(hijo, valor)

def _podar_recursivo(self, nodo_actual, valor):

nodo_actual.hijos = [n for n in nodo_actual.hijos if [Link] != valor]
for hijo in nodo_actual.hijos:
self._podar_recursivo(hijo, valor)

 Injertar: incorporar un árbol como subárbol de otro.

def injertar_subarbol(self, valor, subarbol):

nuevo_nodo = NodoArbolNArio(valor)
nuevo_nodo.hijos = [Link]
self.agregar_elemento(valor)
[Link](nuevo_nodo)

 Enumerar: listar todos los nodos del árbol

def enumerar_nodos(self):
nodos = []
if [Link]:
self._enumerar_recursivo([Link], nodos)
return nodos

def _enumerar_recursivo(self, nodo_actual, nodos):

[Link](nodo_actual.valor)
for hijo in nodo_actual.hijos:
self._enumerar_recursivo(hijo, nodos)

[Link]
© Universidad Alfonso X el Sabio 52
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

 Buscar un elemento: localizar y devolver el contenido de un nodo

def buscar_elemento(self, valor):

return self._buscar_recursivo([Link], valor)

def _buscar_recursivo(self, nodo_actual, valor):

if nodo_actual.valor == valor:
return True
for hijo in nodo_actual.hijos:
if self._buscar_recursivo(hijo, valor):
return True
return False

 Buscar la raíz de un nodo

def buscar_raiz(self, valor):

return self._buscar_raiz_recursivo([Link], valor)

def _buscar_raiz_recursivo(self, nodo_actual, valor):

if nodo_actual.valor == valor:
return nodo_actual
for hijo in nodo_actual.hijos:
resultado = self._buscar_raiz_recursivo(hijo, valor)
if resultado:
return resultado
return None

Como puedes observar, en los árboles hacemos uso intensivo de la recursividad para recorrer el
árbol.

[Link]
© Universidad Alfonso X el Sabio 53
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

3.7. Grafos

En esta ocasión te pido que pienses en un plano de un metro o autobús de tu ciudad más
cercana. Si haces un pequeño ejercicio de abstracción podrás identificar cada una de las
estaciones o paradas como si fueran nodos – de hecho, lo son -, y cada una de las líneas que
conectan dos paradas serían – ¡oh sorpresa! – las aristas.

Ahora que ya lo visualizamos, podemos decir que un grafo es una estructura de datos que se
utiliza para representar relaciones entre elementos. Puedes pensar en un grafo como un
conjunto de nodos que están conectados entre sí mediante enlaces. Los grafos se utilizan para
modelar una amplia variedad de situaciones del mundo real, como redes sociales, sistemas de
navegación, mapas, diagramas de flujo y más.

Podemos definir un grafo como una estructura de datos que consiste en un conjunto finito de
nodos (o vértices) y un conjunto de aristas (o enlaces) que conectan estos nodos. Cada arista
conecta dos nodos y puede tener una dirección (en el caso de un grafo dirigido) o no tenerla (en
el caso de un grafo no dirigido). Además, las aristas pueden tener pesos asociados, que
representan costos, distancias, etc.

Tipos de Grafos
Existen varios tipos de grafos, centrémonos en los principales:

 Grafo no dirigido: Las aristas no tienen dirección.

 Grafo dirigido (digrafo): Las aristas tienen dirección, es decir, van de un vértice a otro.

 Grafo ponderado: Cada arista tiene un peso o costo asociado.

 Grafo no ponderado: Las aristas no tienen pesos.

 Grafo cíclico: Existe al menos un ciclo en el grafo.

 Grafo acíclico: No tiene ciclos.

Terminología de grafos
 Aristas adyacentes: Las aristas adyacentes son dos aristas que comparten un mismo
nodo final. Es decir, ambas aristas están conectadas a un mismo nodo.

 Aristas paralelas: Son dos o más aristas que conectan los mismos dos nodos. En otras
palabras, representan múltiples conexiones entre los mismos nodos.

[Link]
© Universidad Alfonso X el Sabio 54
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

 Aristas cíclicas o bucles: Una arista cíclica o bucle es una arista que conecta un nodo
consigo mismo. Esto significa que un nodo tiene una relación o conexión directa con él
mismo.

 Camino: Un camino en un grafo es una secuencia de nodos en la que cada par de nodos
adyacentes en la secuencia está conectado por una arista. En otras palabras, es una ruta
que se puede seguir desde un nodo inicial a un nodo final pasando por otros nodos
intermedios a lo largo de las aristas.

Tipos de grafos especiales

 Grafo Simple: es un tipo de grafo en el que no hay aristas paralelas ni bucles (aristas que
conectan un nodo consigo mismo). Cada par de nodos está conectado por a lo sumo una
arista.

 Grafo Dirigido (u Orientado): En un grafo dirigido, las aristas tienen una dirección
específica, es decir, tienen un punto de inicio y un punto final. La relación entre dos
nodos va en una dirección definida, como las flechas en un diagrama de flujo.

 Grafo Etiquetado (o Ponderado): En un grafo etiquetado, cada arista tiene una etiqueta
o peso asociado que representa alguna medida o valor. Estos pesos pueden representar
distancias – piensa en las rutas del GPS del coche -, costos, tiempos, etc.

 Grafo Plano: Un grafo plano es aquel que puede dibujarse en el plano (en un papel o
una pantalla) de manera que las aristas no se crucen entre sí. Es decir, no hay
superposición de aristas.

 Grafo Conexo: Un grafo conexo es aquel en el que existe un camino entre cualquier par
de nodos. No importa cuán lejos estén los nodos, siempre es posible llegar de uno a otro
siguiendo las aristas.

 Grafo No Conexo: Un grafo no conexo es aquel en el que al menos dos conjuntos de

nodos están completamente desconectados entre sí, es decir, no hay un camino que los
conecte. El grafo está dividido en partes aisladas.

Usos comunes de los grafos

Los grafos se utilizan en una amplia variedad de aplicaciones en ciencias de la computación y
otros campos debido a su capacidad para representar relaciones complejas entre elementos.
Veamos algunos de los usos más comunes de los grafos:

 Redes Sociales: Los grafos se utilizan para representar y analizar redes sociales, donde
los nodos son individuos y las aristas representan relaciones entre ellos (amigos,
seguidores, etc.).

[Link]
© Universidad Alfonso X el Sabio 55
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

 Sistemas de Recomendación: En plataformas como Netflix, Spotify o Amazon, se utilizan

grafos para identificar y recomendar contenidos basados en preferencias y
comportamientos similares entre usuarios.

 Mapeo y Navegación: Los servicios de mapas utilizan grafos donde los nodos son lugares
y las aristas son caminos o carreteras para encontrar la ruta más corta entre dos puntos.

 Redes de Ordenadores: Los grafos ayudan a representar y analizar estructuras de red,

como la Internet, donde los nodos son computadoras y las aristas son conexiones.

 Búsqueda Web: Los algoritmos de búsqueda, como el algoritmo PageRank de Google,

utilizan grafos para determinar la importancia de una página web basándose en las
páginas que la enlazan.

 Biología Computacional: En genómica y proteómica, se usan grafos para representar

estructuras moleculares y estudiar las interacciones proteína-proteína.

 Electrónica: En diseño de circuitos electrónicos, se utilizan grafos para representar y

analizar circuitos.

 Optimización: Los problemas de flujo de red, como el flujo máximo, son modelados y
resueltos utilizando grafos.

 Teoría de Juegos: Los grafos pueden representar diversos juegos y problemas,

permitiendo su análisis y solución.

 Planificación de Proyectos: Herramientas como el método de la ruta crítica (CPM) y el

método de la cadena crítica usan grafos para representar tareas y dependencias en la
planificación de proyectos.

 Lingüística Computacional: Los árboles de derivación y las redes semánticas en el

procesamiento del lenguaje natural se modelan a menudo como grafos.

 Base de Datos: Las bases de datos basadas en grafos, como Neo4j, se especializan en
almacenar y consultar datos en forma de grafo, lo que es útil para casos donde las
relaciones entre los datos son tan importantes como los datos en sí.
Estos son solo algunos ejemplos de cómo se utilizan los grafos en la vida real. Su aplicabilidad es
vasta y sigue creciendo a medida que emergen nuevos desafíos y tecnologías.

� Usamos los grafos cuando las relaciones entre los datos son tan importantes como
los datos en sí.

[Link]
© Universidad Alfonso X el Sabio 56
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Ventajas y desventajas

Ventajas Desventajas

Representan relaciones complejas entre Pueden ser complicados de procesar (ej.

objetos. algoritmos de camino más corto pueden ser
intensivos en recursos).

Modelan estructuras y sistemas en la vida Requieren más memoria para almacenar

real (redes sociales, rutas de tráfico, web, información de nodos y aristas.
etc.).

Flexibilidad para modelar diferentes tipos de Puede ser difícil de visualizar para grandes
relaciones (ponderadas, no ponderadas, datasets.
dirigidas, no dirigidas).

Aptos para algoritmos de búsqueda y El análisis y la solución de problemas en

optimización. grafos pueden ser complejos.

Soportan operaciones como adición y La representación (por ejemplo, matriz de

eliminación de nodos y aristas. adyacencia) puede no ser eficiente en
términos de espacio para grafos dispersos.

Los grafos son una herramienta poderosa en ciencias de la computación y matemáticas y tienen
aplicaciones en muchas áreas, desde la planificación de rutas y redes hasta la organización de
información y la modelización de sistemas sociales y biológicos.

Matriz de adyacencia
Una matriz de adyacencia es una forma de representar un grafo finito G=(V,E), donde V es un
conjunto de vértices/nodos y E es un conjunto de aristas/edges. Esta matriz es cuadrada (tiene
la misma cantidad de filas que de columnas) y su tamaño es ∣V∣×∣V∣, donde ∣V∣ es el número de
vértices en el grafo.

[Link]
© Universidad Alfonso X el Sabio 57
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Ilustración 4 Ejemplo de matriz de adyacencia. Distancias entre capitales de provincia en España

Veamos otra representación

Ilustración 5 Representación gráfica y mediante matriz de adyacencia de un grafo

Las filas y columnas corresponden a los vértices. El valor almacenado en la celda en la i-ésima
fila y j-ésima columna de la matriz indica la relación entre el i-ésimo vértice y el j-ésimo vértice.

Para un grafo no dirigido:

Si el valor en la posición (i,j) es 1, significa que hay una arista entre los vértices i y j.

Si el valor es 0, significa que no hay arista.

Para un grafo dirigido:

[Link]
© Universidad Alfonso X el Sabio 58
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Si el valor en la posición (i,j) es 1, significa que hay una arista que va del vértice i al vértice j.

Si el valor es 0, significa que no hay arista en esa dirección.

Para grafos ponderados, en lugar de 1, el valor en la matriz de adyacencia es el peso de la arista.

Ilustración 6 Representación de un grafo

La matriz de adyacencia para este grafo es:

A B C D

A 0 1 0 1

B 1 0 1 0

C 0 1 0 1

D 1 0 1 0

Donde:

- La celda (A, B) tiene un valor de 1 porque hay una arista entre A y B.

- La celda (A, C) tiene un valor de 0 porque no hay una arista directa entre A y C.
- ... y así sucesivamente.

Implementación de un grafo
Dentro de las formas de implementar un grafo podemos destacar las siguientes:

 Matriz de adyacencia: En esta representación, usamos una matriz bidimensional donde

las filas y columnas representan nodos. Si existe una arista entre dos nodos, la celda
correspondiente en la matriz tendrá un valor distinto de cero para indicar la conexión.
o Observa que, si el grafo no es dirigido, la matriz es simétrica respecto de su eje
principal

[Link]
© Universidad Alfonso X el Sabio 59
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

 Lista de adyacencia: En esta representación, cada nodo tiene una lista de sus nodos
vecinos. Esto es especialmente útil para grafos dispersos, donde no todas las parejas de
nodos están conectadas.
o Nodo A: [B, D]
o Nodo B: [A, C, D]
o Nodo C: [B, D]
o Nodo D: [A, B, C]

Ilustración 7 Grafo obtenido a partir de la matriz y/o lista de adyacencia. Fuente: elaboración propia

Operaciones sobre grafos

Las operaciones básicas son:

 Agregar nodo

 Agregar arista

 Eliminar nodo

 Eliminar arista

 Verificar conexión: (comprobar si existe un camino entre dos nodos) o recorrer el grafo.

 Vecinos o adyacentes: listar los nodos con los que un nodo determinado tiene conexión
directa

 Grado de un nodo: cantidad de nodos con los que un nodo determinado tiene conexión
directa

[Link]
© Universidad Alfonso X el Sabio 60
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Implementación
Veamos una implementación básica de un grafo.

class Grafo:
'''
Clase Grafo para implementar una estructura de datos de grafo.

Atributos:
nodos (dict): Diccionario que mapea cada nodo a una lista de nodos adyacentes.
'''

def __init__(self):
'''
Inicializa un grafo vacío.
'''
[Link] = {}

def agregar_nodo(self, valor):

'''
Agrega un nodo al grafo.

:param valor: Valor del nodo a agregar.

Si el nodo ya existe en el grafo, no realiza ninguna acción.
'''
# Añade el nodo al diccionario si no existe.
if valor not in [Link]:
[Link][valor] = []

def agregar_arista(self, origen, destino):

'''
Agrega una arista no dirigida al grafo.

:param origen: Nodo de origen de la arista.

:param destino: Nodo de destino de la arista.
Asegura que tanto el nodo de origen como el de destino existan y que la
arista no esté duplicada.
'''
# Verifica que ambos nodos existan y que la arista no esté ya presente.
if origen in [Link] and destino in [Link]:
if destino not in [Link][origen]:
[Link][origen].append(destino)
# Como es un grafo no dirigido, añade la arista en ambos sentidos.

[Link]
© Universidad Alfonso X el Sabio 61
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

[Link][destino].append(origen)

def mostrar_grafo(self):
'''
Imprime una representación del grafo.
Muestra cada nodo y sus nodos adyacentes.
'''
# Recorre cada nodo y sus nodos adyacentes, imprimiéndolos.
for nodo in [Link]:
print(f"{nodo} -> {', '.join(map(str, [Link][nodo]))}")

def vecinos(self, nodo: Any) -> List[Tuple[Any, float]]:

'''
Obtiene los vecinos o nodos adyacentes de un nodo específico en el grafo.

Este método es útil para encontrar todos los nodos que están directamente
conectados a un nodo dado, junto con el peso de las aristas que los conectan.

:param nodo: El nodo para el cual se quieren encontrar los vecinos.

:return: Una lista de tuplas, donde cada tupla representa un vecino y el peso
de la arista que conecta al nodo dado con este vecino. Si el nodo no
tiene vecinos o no existe en el grafo, se devuelve una lista vacía.
'''
return [Link](nodo, [])

def grado_nodo(self, nodo: Any) -> int:

'''
Calcula el grado total de un nodo en el grafo.

En un grafo dirigido, el grado de un nodo es la suma de su grado de entrada y

su grado de salida.
El grado de entrada se refiere al número de aristas que llegan al nodo,
mientras que el grado de salida se refiere al número de aristas que salen del
nodo.

:param nodo: El nodo para el cual se calculará el grado.

:return: El grado total del nodo especificado. Si el nodo no existe en el
grafo, se devuelve 0.
'''
return self.grado_entrada_nodo(nodo) + self.grado_salida_nodo(nodo)
Grafo ponderado

[Link]
© Universidad Alfonso X el Sabio 62
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Veamos cómo sería la matriz de adyacencia de un grafo ponderado. Observa cómo los valores
de la matriz ya no se limitan a valores de 0 ó 1. Fíjate también en cómo se establece el bucle o
arista cíclica en el nodo D.

A B C D

A 0 2 4 0

B 2 0 3 1

C 4 3 0 5

D 0 1 5 3

Ilustración 8 Grafo ponderado. Fuente: elaboración propia

En el caso de grafos ponderados, debemos tener en cuenta que la implementación es algo más
compleja que en los grafos no ponderados. Tenemos que manejar, además de

class GrafoPonderado:
'''
Clase GrafoPonderado para representar un grafo ponderado.

Atributos:

[Link]
© Universidad Alfonso X el Sabio 63
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

grafo (dict): Diccionario que representa el grafo, donde las claves son los
vértices y los valores son diccionarios
que mapean los vértices adyacentes y sus pesos asociados.
'''

def __init__(self):
'''
Inicializa un grafo ponderado vacío.
'''
[Link] = {}

def agregar_vertice(self, vertice: Any) -> None:

'''
Agrega un nuevo vértice al grafo.

:param vertice: El vértice a agregar.

Si el vértice ya existe, no se realiza ninguna acción.
'''
if vertice not in [Link]:
[Link][vertice] = {}

def agregar_arista(self, vertice1: Any, vertice2: Any, peso: float) -> None:
'''
Agrega una arista ponderada entre dos vértices.

:param vertice1: El primer vértice de la arista.

:param vertice2: El segundo vértice de la arista.
:param peso: El peso de la arista.
'''
self.agregar_vertice(vertice1)
self.agregar_vertice(vertice2)
[Link][vertice1][vertice2] = peso
[Link][vertice2][vertice1] = peso # Omitir en caso de un grafo dirigido.

def eliminar_vertice(self, vertice: Any) -> None:

'''
Elimina un vértice del grafo, junto con todas sus aristas adyacentes.

:param vertice: El vértice a eliminar.

'''
if vertice in [Link]:
del [Link][vertice]
for v in [Link]:
if vertice in [Link][v]:

[Link]
© Universidad Alfonso X el Sabio 64
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

del [Link][v][vertice]

def eliminar_arista(self, vertice1: Any, vertice2: Any) -> None:

'''
Elimina una arista entre dos vértices.

:param vertice1: El primer vértice de la arista.

:param vertice2: El segundo vértice de la arista.
'''
if vertice1 in [Link] and vertice2 in [Link]:
if vertice2 in [Link][vertice1]:
del [Link][vertice1][vertice2]
if vertice1 in [Link][vertice2]:
del [Link][vertice2][vertice1]

def obtener_vertices(self) -> List[Any]:

'''
Devuelve una lista de todos los vértices en el grafo.

:return: Lista de vértices del grafo.

'''
return list([Link]())

def obtener_aristas(self) -> List[Tuple[Any, Any, float]]:

'''
Devuelve una lista de todas las aristas en el grafo, junto con sus pesos.

:return: Lista de tuplas, cada una representando una arista y su peso.

'''
aristas = []
for vertice1 in [Link]:
for vertice2, peso in [Link][vertice1].items():
[Link]((vertice1, vertice2, peso))
return aristas

def obtener_peso_arista(self, vertice1: Any, vertice2: Any) -> float:

'''
Obtiene el peso de una arista específica.

:param vertice1: El primer vértice de la arista.

:param vertice2: El segundo vértice de la arista.
:return: El peso de la arista. Si la arista no existe, devuelve None.
'''
if vertice1 in [Link] and vertice2 in [Link][vertice1]:

[Link]
© Universidad Alfonso X el Sabio 65
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

return [Link][vertice1][vertice2]
else:
return None

def __str__(self) -> str:

'''
Representación en cadena del grafo.

:return: Una cadena que representa el grafo, mostrando cada arista y su peso.
'''
resultado = ""
for vertice1 in [Link]:
for vertice2, peso in [Link][vertice1].items():
resultado += f"{vertice1} --({peso})--> {vertice2}\n"
return resultado

Si seguimos con el ejemplo anteriormente establecido en la matriz de adyacencia, podríamos

crearlo de la siguiente forma:

# Crear una instancia del grafo ponderado

grafo = GrafoPonderado()

# Agregar nodos y aristas con pesos

grafo.agregar_arista('A', 'B', 2)
grafo.agregar_arista('A', 'C', 4)
grafo.agregar_arista('B', 'C', 3)
grafo.agregar_arista('B', 'D', 1)
grafo.agregar_arista('C', 'D', 5)
grafo.agregar_arista('D', 'D', 3)

# Imprimir el grafo
print("Grafo Ponderado:")
print(grafo)

# Obtener el peso de una arista específica (por ejemplo, entre A y B)

peso_AB = grafo.obtener_peso_arista('A', 'B')
print("Peso de la arista entre A y B:", peso_AB)

# Eliminar una arista (por ejemplo, entre A y B)

grafo.eliminar_arista('A', 'B')
print("Después de eliminar la arista entre A y B:")

[Link]
© Universidad Alfonso X el Sabio 66
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

print(grafo)

Grafo dirigido
La diferencia reside en que las aristas sí tienen dirección, es decir, si hay una arista entre el nodo
A y el nodo B, no necesariamente hay hay una arista entre el nodo B y el nodo A. A continuación,
vemos una implementación básica de un grafo dirigido utilizando diccionarios en Python:

class GrafoDirigido:
'''
Clase GrafoDirigido para representar un grafo dirigido.

Atributos:
nodos (dict): Diccionario que representa el grafo, mapeando cada nodo a una lista
de nodos a los que se dirige.
'''

def __init__(self):
'''
Inicializa un grafo dirigido vacío.
'''
[Link] = {}

def agregar_nodo(self, valor: Any) -> None:

'''
Agrega un nuevo nodo al grafo si aún no existe.

:param valor: Valor o identificador del nodo a agregar.

Si el nodo ya existe en el grafo, no se realiza ninguna acción.
'''
if valor not in [Link]:
[Link][valor] = []

def agregar_arista(self, origen: Any, destino: Any) -> None:

'''
Agrega una arista dirigida del nodo 'origen' al nodo 'destino'.

:param origen: Nodo desde el cual se origina la arista.

:param destino: Nodo al cual se dirige la arista.
Asegura que tanto el nodo de origen como el de destino existan y que la
arista no esté duplicada.
'''
if origen in [Link] and destino in [Link]:

[Link]
© Universidad Alfonso X el Sabio 67
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

if destino not in [Link][origen]:

[Link][origen].append(destino)

def mostrar_grafo(self) -> None:

'''
Imprime una representación del grafo.

Muestra cada nodo junto con una lista de nodos a los cuales se dirige.
Esta representación ayuda a visualizar las conexiones del grafo dirigido.
'''
for nodo in [Link]:
print(f"{nodo} -> {', '.join(map(str, [Link][nodo]))}")

Ejercicio de repaso
Sistema de recomendación de rutas en una ciudad
Escenario:
Te has unido a un equipo encargado de desarrollar una aplicación móvil de navegación para una
ciudad. El objetivo principal de esta aplicación es ofrecer a los usuarios diferentes rutas entre
dos puntos de la ciudad, considerando diferentes criterios como la distancia más corta, el menor
tiempo o el número mínimo de paradas. La ciudad se modelará usando un grafo, donde cada
nodo representa un punto de interés o una intersección y cada arista representa un camino
entre esos dos puntos.

Descripción del ejercicio:

 Modelado del Grafo:

o Crea una clase Nodo que tenga al menos los siguientes atributos: nombre y
conexiones (una lista o diccionario de nodos adyacentes con el peso o
distancia entre ellos).
o Crea una clase GrafoCiudad que represente el grafo de la ciudad. Esta clase
debe tener métodos para agregar nodos, conectar nodos y obtener rutas.

 Funcionalidades a implementar:
o agregar_punto(nombre): Permite agregar un punto de interés o
intersección a la ciudad.
o conectar_puntos(nombre_a, nombre_b, distancia): Conecta
dos puntos con una distancia específica.

[Link]
© Universidad Alfonso X el Sabio 68
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

o ruta_mas_corta(origen, destino): Dados dos puntos, devuelve la

ruta más corta entre ellos basada en la distancia.
o ruta_menos_paradas(origen, destino): Dados dos puntos,
devuelve la ruta con el menor número de paradas entre ellos.
o eliminar_punto(nombre): Elimina un punto y todas sus conexiones.

 Caso práctico:
o Crea un pequeño mapa de una ciudad ficticia con al menos 10 puntos de interés.
o Agrega conexiones entre estos puntos con diferentes distancias.
o Implementa y prueba los algoritmos para obtener la ruta más corta y la ruta con
menos paradas entre diferentes puntos de interés.

Nota: Para resolver este ejercicio, podrías considerar algoritmos como el de Dijkstra (lo
encontrarás en unidades posteriores) para determinar la ruta más corta entre dos puntos.

[Link]
© Universidad Alfonso X el Sabio 69
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

3.8. Tablas de Hash

A menudo utilizamos códigos hash en nuestro día a día, aunque quizás no seamos conscientes
de ello, el más frecuente es el de la letra del DNI, aunque también las usamos en multitud de
bases de datos, en la caché de los navegadores, para detectar duplicados en una colección de
elementos complejos o para acelerar procesos de búsqueda en nuestro sistema de archivos.

Vídeo
Calcular la letra del DNI en segundos
[Link]

Las tablas hash son como una especie de "caja mágica" que nos ayuda a guardar información de
manera rápida y eficiente. Imagina que tienes una caja con muchos compartimentos, y cada
compartimento tiene un número único. Puedes poner cosas dentro de estos compartimentos y
luego encontrarlas muy rápido cuando las necesites. Eso es básicamente lo que hace una tabla
hash, pero en lugar de compartimentos, usa números especiales para guardar y encontrar
información.

Las tablas hash utilizan una función especial, llamada función de hash, para convertir la
información que queremos guardar en un número. Esta función de hash toma la información y
la transforma en un número único. Luego, ese número se usa como "dirección" para encontrar
el lugar donde se guarda la información en la tabla hash.

Imagina que tienes un libro que quieres guardar en tu biblioteca. En lugar de buscar el libro en
todas las estanterías, puedes usar la función de hash para obtener un número único para ese
libro y luego guardarlo en la estantería con ese número. Cuando quieras encontrar el libro,
simplemente usas la función de hash nuevamente para obtener el número y vas directamente
a la estantería correcta, ¡así encuentras el libro mucho más rápido! Pero ¡espera! Eso es una
biblioteca ¿no?

Implementación de tablas hash

1. Crear la tabla:
• Primero, necesitas crear una tabla vacía con compartimentos. El número de
compartimentos depende de la cantidad de información que planeas guardar.
Cuantos más compartimentos tengas, más rápido será encontrar la información,
pero también requerirá más memoria.

[Link]
© Universidad Alfonso X el Sabio 70
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

2. Diseñar la función de hash:

• Debes crear una función de hash que tome la información que quieres guardar
y la convierta en un número único. Esta función debe ser constante, es decir,
siempre debe dar el mismo número para la misma información.
3. Guardar la información:
• Cuando quieras guardar algo, aplicas la función de hash a esa información y
obtienes un número. Luego, colocas la información en el compartimento
correspondiente al número obtenido.
4. Buscar la información:
• Cuando necesites encontrar la información, aplicas la función de hash
nuevamente a la información que estás buscando para obtener el número.
Luego, vas directamente al compartimento con ese número y ahí encontrarás
lo que buscas.
Es importante que recuerdes que, aunque las tablas hash son muy eficientes para buscar
información, es necesario tener cuidado al diseñar la función de hash para evitar colisiones, es
decir, que dos piezas de información diferentes obtengan el mismo número. Cuando eso sucede,
debemos tomar medidas para resolver la colisión y garantizar que la información se almacene
de manera adecuada.

Veamos el código de una implementación básica

class TablaHash:
def __init__(self, capacidad_inicial=10):
[Link] = capacidad_inicial
[Link] = 0 # Número de elementos en la tabla
[Link] = [None] * [Link] # Inicializa la tabla con valores nulos

def _hash(self, clave):

# Una función hash simple para este ejemplo, podría ser más sofisticada en la
práctica.
return hash(clave) % [Link]

def agregar(self, clave, valor):

indice = self._hash(clave)

# Si el índice está ocupado, resuelve colisiones con manejo de colisiones.

if [Link][indice] is None:
[Link][indice] = [(clave, valor)]
else:
for i, (c, v) in enumerate([Link][indice]):
if c == clave:

[Link]
© Universidad Alfonso X el Sabio 71
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

[Link][indice][i] = (clave, valor)

break
else:
[Link][indice].append((clave, valor))

[Link] += 1

# Verificar si se necesita redimensionar la tabla.

if [Link] > [Link] * 0.7:
self._redimensionar()

def obtener(self, clave):

indice = self._hash(clave)
if [Link][indice] is not None:
for c, v in [Link][indice]:
if c == clave:
return v
raise KeyError(f"La clave '{clave}' no se encuentra en la tabla hash.")

def eliminar(self, clave):

indice = self._hash(clave)
if [Link][indice] is not None:
for i, (c, v) in enumerate([Link][indice]):
if c == clave:
del [Link][indice][i]
[Link] -= 1
return
raise KeyError(f"La clave '{clave}' no se encuentra en la tabla hash.")

def _redimensionar(self):
# Duplica la capacidad de la tabla y reorganiza los elementos.
nueva_capacidad = [Link] * 2
nueva_tabla = [None] * nueva_capacidad

for lista in [Link]:

if lista is not None:
for clave, valor in lista:
nuevo_indice = hash(clave) % nueva_capacidad
if nueva_tabla[nuevo_indice] is None:
nueva_tabla[nuevo_indice] = [(clave, valor)]
else:
nueva_tabla[nuevo_indice].append((clave, valor))

[Link] = nueva_capacidad

[Link]
© Universidad Alfonso X el Sabio 72
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

[Link] = nueva_tabla

[Link]
© Universidad Alfonso X el Sabio 73
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

3.9. Montículos

Un montículo (heap) es una estructura de datos de tipo árbol binario especializado que satisface
la propiedad del montículo. Esta propiedad implica un orden específico entre nodos padre e
hijo. Hay dos tipos principales de montículos:

• Montículo máximo (Max Heap): Para cualquier nodo dado, el valor de ese nodo es
mayor o igual que los valores de sus hijos.
• Montículo mínimo (Min Heap): Para cualquier nodo dado, el valor de ese nodo es
menor o igual que los valores de sus hijos.
Las operaciones clave en un montículo incluyen la inserción, la eliminación y la obtención del
elemento máximo (en un Max Heap) o mínimo (en un Min Heap). Los montículos son esenciales
para algoritmos como el de ordenación por montículos (Heapsort) y algoritmos de ruta más
corta como Dijkstra.

Operaciones básicas
Las operaciones básicas asociadas a un montículo (heap) son:

1. Inserción (Insert o Push):

o Se agrega un nuevo elemento al final del montículo (es decir, al siguiente
espacio disponible en el arreglo).
o Luego, se ajusta el montículo para asegurar que mantenga sus propiedades,
usando el proceso de "burbujeo" hacia arriba (bubble-up).
2. Eliminación del elemento máximo/mínimo (Delete Max/Delete Min o Pop):
o Se elimina el elemento en la raíz del montículo, que es el elemento máximo en
un montículo máximo o el elemento mínimo en un montículo mínimo.
o El último elemento en el montículo se coloca temporalmente en la raíz.
o Se ajusta el montículo para mantener sus propiedades, usando el proceso de
"hundimiento" (sink-down).
3. Obtener el elemento máximo/mínimo (Max/Min o Peek):
o Retorna el elemento en la raíz del montículo sin eliminarlo. Esta operación se
puede realizar en tiempo constante, ya que el elemento está siempre en la
raíz.
4. Heapify o Sink_Down:
o Es un proceso para convertir una lista no ordenada en un montículo. Es
especialmente útil cuando se tiene un conjunto de elementos y se desea
construir un montículo rápidamente a partir de ellos.
5. Aumentar/decrementar clave (Increase/Decrease Key):
o Modifica el valor de un elemento en el montículo y luego reajusta el montículo
para mantener sus propiedades.
6. Unión (Merge o Union):

[Link]
© Universidad Alfonso X el Sabio 74
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

o Combina dos montículos en un solo montículo que mantiene las propiedades

de montículo.
7. Tamaño (Size):
o Retorna el número de elementos en el montículo.
8. Está vacío (Is Empty):
o Verifica si el montículo está vacío.
9. Borrar (Delete):
o Elimina un elemento arbitrario del montículo. Esta operación no es tan común
como Delete Max/Min, y después de eliminar el elemento, se reajusta el
montículo para mantener sus propiedades.

Estas son las operaciones básicas asociadas a los montículos. Es importante señalar que la
eficiencia de estas operaciones es lo que hace que los montículos sean tan útiles en algoritmos
como los algoritmos de ruta más corta y algoritmos de ordenación como heapsort.

Usos comunes de los montículos

• Implementación de colas de prioridad.

• Algoritmos de ordenación.
• Algoritmos de ruta más corta.

Propiedades de los montículos:

• Suelen implementarse usando arrays o listas. El nodo raíz está en el índice 0.

• Para cualquier nodo en el índice i,
o Su hijo izquierdo está en el índice 2i + 1
o Su hijo derecho está en el índice 2i + 2
o Su padre está en el índice (i-1) // 2 (división entera)

Ventajas y Desventajas

Ventajas Desventajas

Alta eficiencia en operaciones de inserción y No es eficiente para operaciones de

eliminación. búsqueda (excepto el máximo o mínimo).

Aprovecha bien la localidad de referencia en Los montículos binarios tienen una estructura
memoria, lo que lo hace relativamente rápido menos rígida que los árboles de búsqueda
en la práctica binaria, por lo que podrían no ser tan
intuitivos.

[Link]
© Universidad Alfonso X el Sabio 75
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Garantiza un tiempo constante para Si se requiere una estructura con operaciones

encontrar el elemento máximo o mínimo. arbitrarias de búsqueda, las estructuras como
árboles binarios de búsqueda o tablas hash
podrían ser más adecuadas.

Puede ser implementado eficientemente

utilizando un array.

Implementación
Comenzamos con la implementación de una clase Empleado a modo de ejemplo – o plantilla
de base - utilizada como valor de los nodos

Clase Empleado

class Empleado:
'''
Clase Empleado para representar la información de un empleado.

Atributos:
num_empleado (int): Número identificador del empleado.
nombre (str): Nombre del empleado.
apellidos (str): Apellidos del empleado.
dni (str): Documento Nacional de Identidad del empleado.
fecha_nac (str): Fecha de nacimiento del empleado.
'''

def __init__(self, num_empleado, nombre, apellidos, dni, fecha_nac):

'''
Inicializa un nuevo empleado con sus datos personales.

:param num_empleado: Número identificador del empleado.

:param nombre: Nombre del empleado.
:param apellidos: Apellidos del empleado.
:param dni: DNI del empleado.
:param fecha_nac: Fecha de nacimiento del empleado.
'''
self.num_empleado = num_empleado
[Link] = nombre
[Link] = apellidos
[Link] = dni
self.fecha_nac = fecha_nac

[Link]
© Universidad Alfonso X el Sabio 76
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

def compare_to(self, empleado1):

'''
Compara este empleado con otro según su número identificador.

:param empleado1: Objeto Empleado a comparar.

:return: 1 si este empleado tiene un número mayor, -1 si menor, 0 si son
iguales.
'''
if self.num_empleado > empleado1.num_empleado:
return 1
elif self.num_empleado < empleado1.num_empleado:
return -1
else:
return 0

def equals(self, empleado1) -> bool:

'''
Determina si dos empleados son iguales basándose en criterios definidos.
Actualmente, este método no implementa una lógica específica.

:param empleado1: Empleado con el cual comparar.

:return: True si se consideran iguales, False en caso contrario.
'''
resultado = True
# Aquí irían los criterios de igualdad
return resultado

def __str__(self):
'''
Representación en cadena del empleado, mostrando su número identificador.

:return: Representación en cadena del número identificador del empleado.

'''
return str(self.num_empleado)

def __lt__(self, other):

'''
Sobrecarga del operador < para comparar empleados según su número
identificador.

:param other: Otro objeto Empleado para la comparación.

:return: True si este empleado tiene un número identificador menor que
'other'.
'''

[Link]
© Universidad Alfonso X el Sabio 77
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

return self.num_empleado < other.num_empleado

def __le__(self, other):

'''
Sobrecarga del operador <= para comparar empleados según su número
identificador.

:param other: Otro objeto Empleado para la comparación.

:return: True si este empleado tiene un número identificador menor o igual
que 'other'.
'''
return self.num_empleado <= other.num_empleado

def __gt__(self, other):

'''
Sobrecarga del operador > para comparar empleados según su número
identificador.

:param other: Otro objeto Empleado para la comparación.

:return: True si este empleado tiene un número identificador mayor que
'other'.
'''
return self.num_empleado > other.num_empleado

# Comentado ya que parece haber un error en la implementación

def __ge__(self, other):
'''
Sobrecarga del operador >= para comparar empleados según su número
identificador.

:param other: Otro objeto Empleado para la comparación.

:return: True si este empleado tiene un número identificador mayor o igual
que 'other'.
'''
return self.num_empleado >= other.num_empleado

def __eq__(self, other):

'''
Sobrecarga del operador == para comparar empleados según su número
identificador.

:param other: Otro objeto Empleado para la comparación.

:return: True si este empleado tiene un número identificador igual a 'other'.
'''

[Link]
© Universidad Alfonso X el Sabio 78
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

return self.num_empleado == other.num_empleado

def __ne__(self, other):

'''
Sobrecarga del operador != para comparar empleados según su número
identificador.

:param other: Otro objeto Empleado para la comparación.

:return: True si este empleado tiene un número identificador distinto de
'other'.
'''
return not(self.__eq__(other))

Clase Nodo

Continuamos con la clase Nodo que nos permitirá crear la estructura básica de almacenamiento
de la información

class Nodo:
'''
Clase Nodo para representar un nodo en estructuras de datos basadas en árboles.

Atributos:
valor (Any): El valor almacenado en el nodo.
hijo_izquierda (Nodo): Referencia al hijo izquierdo del nodo.
hijo_derecha (Nodo): Referencia al hijo derecho del nodo.
'''

def __init__(self, valor):

'''
Inicializa un nuevo nodo.

:param valor: El valor a almacenar en el nodo.

'''
[Link] = valor # Almacena el valor del nodo
self.hijo_izquierda = None # Inicialmente no tiene hijo izquierdo
self.hijo_derecha = None # Inicialmente no tiene hijo derecho

Clase MaxHeap o de Montículo Máximo

[Link]
© Universidad Alfonso X el Sabio 79
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Recuerda que un montículo máximo (Max Heap) cumple que el nodo padre siempre es mayor
que sus nodos hijos, mientras que en un Min Heap es al contrario.

from typing import Any

from Nodo import Nodo

class MaxHeap:
'''
Clase MaxHeap para representar un montículo máximo.
En un montículo máximo, cada nodo padre es mayor o igual que sus hijos.
'''

def __init__(self) -> None:

# Inicializa el montículo como una lista vacía
[Link] = []

def _parent(self, index) -> int:

'''
Devuelve el índice del padre de un nodo dado.
:param index: Índice del nodo hijo.
:return: Índice del nodo padre.
'''
return (index - 1) // 2

def _bubble_up(self, index: int):

'''
Realiza la operación de flotación (bubble up) para mantener la propiedad del
montículo.
Mueve un nodo hacia arriba en el montículo hasta que se restablecen las
propiedades del montículo.
:param index: Índice del nodo que se está flotando.
'''
padre = self._parent(index)
while padre >= 0 and [Link][padre] < [Link][index]:
[Link][padre], [Link][index] = [Link][index], [Link][padre]
index = padre
padre = self._parent(index)

def push(self, val: Any) -> None:

'''
Inserta un nuevo valor en el montículo.
:param val: Valor a insertar.
'''
nuevoNodo = Nodo(val)

[Link]
© Universidad Alfonso X el Sabio 80
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

[Link](nuevoNodo)
self._bubble_up(len([Link]) - 1)

def peek(self) -> Nodo:

'''
Devuelve el valor del nodo raíz sin eliminarlo.
:return: Nodo raíz del montículo.
'''
if self.is_empty():
return None
return [Link][0]

def pop(self) -> Nodo:

'''
Elimina y devuelve el nodo raíz del montículo.
Reemplaza el nodo raíz con el último nodo y realiza un sink down para
mantener las propiedades del montículo.
:return: Nodo raíz eliminado.
'''
if self.is_empty():
return None
if len([Link]) == 1:
return [Link]()

raiz = [Link][0]
[Link][0] = [Link]()
self._sink_down(0)
return raiz

def _left_child(self, index: int) -> int:

'''
Devuelve el índice del hijo izquierdo del nodo dado.
:param index: Índice del nodo padre.
:return: Índice del hijo izquierdo.
'''
return 2 * index + 1

def _right_child(self, index: int) -> int:

'''
Devuelve el índice del hijo derecho del nodo dado.
:param index: Índice del nodo padre.
:return: Índice del hijo derecho.
'''
return 2 * index + 2

[Link]
© Universidad Alfonso X el Sabio 81
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

def _sink_down(self, index: int):

'''
Realiza la operación de hundimiento (sink down) para mantener la propiedad
del montículo.
Mueve un nodo hacia abajo en el montículo hasta que se restablecen las
propiedades del montículo.
:param index: Índice del nodo que se está hundiendo.
'''
mayor = index
izqda = self._left_child(index)
dcha = self._right_child(index)

# Compara con el hijo izquierdo

if izqda < len([Link]) and [Link][izqda] > [Link][mayor]:
mayor = izqda

# Compara con el hijo derecho

if dcha < len([Link]) and [Link][dcha] > [Link][mayor]:
mayor = dcha

# Realiza el intercambio si es necesario y continúa hundiendo

if mayor != index:
[Link][index], [Link][mayor] = [Link][mayor], [Link][index]
self._sink_down(mayor)

def size(self) -> int:

'''
Devuelve el número de elementos en el montículo.
:return: Tamaño del montículo.
'''
return len([Link])

def is_empty(self) -> bool:

'''
Verifica si el montículo está vacío.
:return: True si el montículo está vacío, False en caso contrario.
'''
return len([Link]) == 0

def find_value(self, value: Any) -> int:

'''
Busca un valor en el montículo y devuelve su índice.
:param value: Valor a buscar.

[Link]
© Universidad Alfonso X el Sabio 82
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

:return: Índice del valor en el montículo, o -1 si no se encuentra.

'''
for index, nodo in enumerate([Link]):
if value == [Link]:
return index
return -1

def delete_node(self, value: Any) -> None:

'''
Elimina un nodo con un valor específico del montículo.
:param value: Valor del nodo a eliminar.
'''
index = self.find_value(value)
if index < 0:
print('Valor no encontrado')
return

# Intercambia con el último nodo y lo elimina

[Link][index], [Link][-1] = [Link][-1], [Link][index]
[Link]()

# Reajusta el montículo
for i in range(([Link]() // 2) - 1, -1, -1):
self._sink_down(i)

def increase_value(self, index: int, new_value: Any) -> None:

'''
Aumenta el valor de un nodo en el montículo.
:param index: Índice del nodo a aumentar.
:param new_value: Nuevo valor del nodo.
'''
if new_value < [Link][index].value:
raise ValueError("El nuevo valor es menor que el actual")
[Link][index].value = new_value
self._bubble_up(index)

def decrease_value(self, index: int, new_value: Any) -> None:

'''
Disminuye el valor de un nodo en el montículo.
:param index: Índice del nodo a disminuir.
:param new_value: Nuevo valor del nodo.
'''
if new_value > [Link][index].value:
raise ValueError("El nuevo valor es mayor que el actual")

[Link]
© Universidad Alfonso X el Sabio 83
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

[Link][index].value = new_value
self._sink_down(index)

def build_heap(self, lista: list) -> None:

'''
Construye un montículo a partir de una lista dada.
:param lista: Lista de valores para construir el montículo.
'''
[Link] = [Nodo(item) for item in lista]
for i in range((len([Link]) // 2) - 1, -1, -1):
self._sink_down(i)

def merge_heaps(self, list1: list, list2: list) -> None:

'''
Combina dos montículos en uno.
:param list1: Primer montículo (o lista) a combinar.
:param list2: Segundo montículo (o lista) a combinar.
'''
if list1 is None:
list1 = [Link]
new_list = list1 + list2
self.build_heap(new_list)

Clase MinHeap o de Montículo Mínimo

Un montículo mínimo (Min Heap) es similar en estructura a un montículo máximo (Max Heap).
La principal diferencia radica en la propiedad de ordenación: en un Min Heap, el nodo padre
siempre es menor que sus nodos hijos, mientras que en un Max Heap es al contrario.

Dado esto, la principal diferencia en la implementación se encuentra en las funciones

_bubble_up y _sink_down, donde las comparaciones se invierten.

Veamos las diferencias con respecto del Max Heap:

from typing import Any

from Nodo import Nodo

class MinHeap:
'''
Clase MinHeap para representar un montículo mínimo.
En un montículo mínimo, cada nodo es menor que sus hijos.

[Link]
© Universidad Alfonso X el Sabio 84
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

'''

def __init__(self) -> None:

# Inicializa el montículo como una lista vacía
[Link] = []

def _sink_down(self, index: int) -> None:

'''
Realiza la operación de hundimiento (sink down) para mantener la propiedad
del montículo mínimo.
Mueve un nodo hacia abajo en el montículo hasta que se restablecen las
propiedades del montículo mínimo.
:param index: Índice del nodo que se está hundiendo.
'''
menor = index
izqda = self._left_child(index)
dcha = self._right_child(index)

# Comparar con hijo izquierdo

if izqda < len([Link]) and [Link][izqda] < [Link][menor]:
menor = izqda

# Comparar con hijo derecho

if dcha < len([Link]) and [Link][dcha] < [Link][menor]:
menor = dcha

if menor != index:
[Link][menor], [Link][index] = [Link][index], [Link][menor]
self._sink_down(menor)

def _bubble_up(self, index: int):

'''
Realiza la operación de flotación (bubble up) para mantener la propiedad del
montículo mínimo.
Mueve un nodo hacia arriba en el montículo hasta que se restablecen las
propiedades del montículo mínimo.
:param index: Índice del nodo que se está flotando.
'''
padre = self._parent(index)
while padre > 0 and [Link][padre] > [Link][index]:
[Link][padre], [Link][index] = [Link][index], [Link][padre]
index = padre
padre = self._parent(index)

[Link]
© Universidad Alfonso X el Sabio 85
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

def _parent(self, index: int) -> int:

'''
Devuelve el índice del padre de un nodo dado.
:param index: Índice del nodo hijo.
:return: Índice del nodo padre.
'''
return (index - 1) // 2

def _left_child(self, index: int):

'''
Devuelve el índice del hijo izquierdo del nodo dado.
:param index: Índice del nodo padre.
:return: Índice del hijo izquierdo.
'''
return 2 * index + 1

def _right_child(self, index: int):

'''
Devuelve el índice del hijo derecho del nodo dado.
:param index: Índice del nodo padre.
:return: Índice del hijo derecho.
'''
return 2 * index + 2

def push(self, val: Any) -> None:

'''
Inserta un nuevo valor en el montículo.
:param val: Valor a insertar.
'''
nuevoNodo = Nodo(val)
[Link](nuevoNodo)
self._bubble_up(len([Link]) - 1)

def peek(self) -> Nodo:

'''
Devuelve el valor del nodo raíz sin eliminarlo.
:return: Nodo raíz del montículo.
'''
if self.is_empty():
return None
return [Link][0]

def pop(self):
'''

[Link]
© Universidad Alfonso X el Sabio 86
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Elimina y devuelve el nodo raíz del montículo.

Reemplaza el nodo raíz con el último nodo y realiza un sink down para
mantener las propiedades del montículo.
:return: Nodo raíz eliminado.
'''
if self.is_empty():
return None
if len([Link]) == 1:
return [Link]()
raiz = [Link][0]
[Link][0] = [Link]()
self._sink_down(0)
return raiz

def size(self) -> int:

'''
Devuelve el número de elementos en el montículo.
:return: Tamaño del montículo.
'''
return len([Link])

def is_empty(self) -> bool:

'''
Verifica si el montículo está vacío.
:return: True si el montículo está vacío, False en caso contrario.
'''
return len([Link]) == 0

def find_value(self, value: Any) -> int:

'''
Busca un valor en el montículo y devuelve su índice.
:param value: Valor a buscar.
:return: Índice del valor en el montículo, o -1 si no se encuentra.
'''
for index, nodo in enumerate([Link]):
if value == [Link]:
return index
return -1

def delete_node(self, value: Any) -> None:

'''
Elimina un nodo con un valor específico del montículo.
:param value: Valor del nodo a eliminar.
'''

[Link]
© Universidad Alfonso X el Sabio 87
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

index = self.find_value(value)
if index < 0:
print('Valor no encontrado')
return

# Intercambia con el último nodo y lo elimina

[Link][index], [Link][-1] = [Link][-1], [Link][index]
[Link]()

# Reajusta el montículo
for i in range(([Link]() // 2) - 1, -1, -1):
self._sink_down(i)

def increase_value(self, index: int, new_value: Any) -> None:

'''
Aumenta el valor de un nodo en el montículo.
:param index: Índice del nodo a aumentar.
:param new_value: Nuevo valor del nodo.
'''
if new_value < [Link][index].valor:
raise ValueError("El nuevo valor es menor que el actual")
[Link][index].valor = new_value
self._bubble_up(index)

def decrease_value(self, index: int, new_value: Any) -> None:

'''
Disminuye el valor de un nodo en el montículo.
:param index: Índice del nodo a disminuir.
:param new_value: Nuevo valor del nodo.
'''
if new_value > [Link][index].valor:
raise ValueError("El nuevo valor es mayor que el actual")
[Link][index].valor = new_value
self._sink_down(index)

def build_heap(self, lista: list) -> None:

'''
Construye un montículo a partir de una lista dada.
:param lista: Lista de valores para construir el montículo.
'''
[Link] = [Nodo(item) for item in lista]
for i in range((len([Link]) // 2) - 1, -1, -1):
self._sink_down(i)

[Link]
© Universidad Alfonso X el Sabio 88
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

def merge_heaps(self, list1: list, list2: list) -> None:

'''
Combina dos montículos en uno.
:param list1: Primer montículo (o lista) a combinar.
:param list2: Segundo montículo (o lista) a combinar.
'''
if list1 is None:
list1 = [Link]
new_list = list1 + list2
self.build_heap(new_list)

Implementación basada en herencia

Es posible -y a menudo es una buena práctica- diseñar una clase genérica Heap y luego crear
clases MaxHeap y MinHeap que hereden de ella. Esto permite reutilizar código y facilita el
mantenimiento y la extensibilidad. La clase base Heap puede implementar la lógica común de
los montículos, mientras que MaxHeap y MinHeap pueden personalizar el comportamiento
específico para montículos máximos y mínimos, respectivamente.

Veamos un ejemplo de cómo podríamos estructurar estas clases:

Heap es la clase base que implementa la estructura y las operaciones comunes de un montículo.
Acepta una función de comparación (comparison_func) que determina cómo se comparan
los elementos (por ejemplo, para un montículo máximo o mínimo).

MaxHeap y MinHeap son subclases de Heap que especifican la lógica de comparación para
montículos máximos y mínimos, respectivamente. La función lambda pasada a
super().__init__ en cada subclase determina el comportamiento del montículo (máximo
o mínimo).

Esta estructura aprovecha la herencia y la reutilización del código, lo que nos facilita la gestión
y mantenimiento del código relacionado con los montículos.

[Link]
© Universidad Alfonso X el Sabio 89
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Clase base Heap:

class Heap:
'''
Clase base Heap para implementar la estructura y operaciones comunes de un
montículo.

Atributos:
heap (list): Lista para almacenar los elementos del montículo.
compare (function): Función de comparación para determinar el ordenamiento en el
montículo.
'''

def __init__(self, comparison_func):

'''
Inicializa un montículo con una función de comparación específica.

:param comparison_func: Una función lambda que define la relación de orden

entre los elementos del montículo.
'''
[Link] = []
[Link] = comparison_func

def _parent(self, index):

'''
Devuelve el índice del padre de un nodo dado.

:param index: Índice del nodo hijo.

:return: Índice del nodo padre.
'''
return (index - 1) // 2

def _left_child(self, index):

'''
Devuelve el índice del hijo izquierdo del nodo dado.

:param index: Índice del nodo padre.

:return: Índice del hijo izquierdo.
'''
return 2 * index + 1

def _right_child(self, index):

'''
Devuelve el índice del hijo derecho del nodo dado.

[Link]
© Universidad Alfonso X el Sabio 90
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

:param index: Índice del nodo padre.

:return: Índice del hijo derecho.
'''
return 2 * index + 2

def _bubble_up(self, index):

'''
Realiza la operación de flotación (bubble up) para mantener la propiedad del
montículo.
Mueve un nodo hacia arriba en el montículo hasta que se restablecen las
propiedades del montículo.

:param index: Índice del nodo que se está flotando.

'''
parent = self._parent(index)
while index > 0 and [Link]([Link][parent], [Link][index]):
[Link][index], [Link][parent] = [Link][parent], [Link][index]
index = parent
parent = self._parent(index)

def _sink_down(self, index):

'''
Realiza la operación de hundimiento (sink down) para mantener la propiedad
del montículo.
Mueve un nodo hacia abajo en el montículo hasta que se restablecen las
propiedades del montículo.

:param index: Índice del nodo que se está hundiendo.

'''
size = len([Link])
element = index

while True:
left = self._left_child(index)
right = self._right_child(index)

if left < size and [Link]([Link][element], [Link][left]):

element = left

if right < size and [Link]([Link][element], [Link][right]):

element = right

if element != index:

[Link]
© Universidad Alfonso X el Sabio 91
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

[Link][element], [Link][index] = [Link][index],

[Link][element]
index = element
else:
break

def push(self, item):

'''
Inserta un nuevo elemento en el montículo.

:param item: Elemento a insertar en el montículo.

'''
[Link](item)
self._bubble_up(len([Link]) - 1)

def pop(self):
'''
Elimina y devuelve el elemento en la cima del montículo.

:return: Elemento en la cima del montículo. Si el montículo está vacío,

devuelve None.
'''
if not [Link]:
return None

item = [Link][0]
last = [Link]()

if [Link]:
[Link][0] = last
self._sink_down(0)

return item

def peek(self):
'''
Devuelve el elemento en la cima del montículo sin eliminarlo.

:return: Elemento en la cima del montículo. Si el montículo está vacío,

devuelve None.
'''
if not [Link]:
return None
return [Link][0]

[Link]
© Universidad Alfonso X el Sabio 92
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

def size(self):
'''
Devuelve el número de elementos en el montículo.

:return: Número de elementos en el montículo.

'''
return len([Link])

def is_empty(self):
'''
Verifica si el montículo está vacío.

:return: True si el montículo está vacío, False en caso contrario.

'''
return len([Link]) == 0

Clase base MaxHeap:

class MaxHeap(Heap):
'''
Clase MaxHeap para implementar un montículo máximo, donde cada nodo padre es
mayor que sus hijos.
Hereda de la clase Heap.
'''

def __init__(self):
'''
Inicializa un montículo máximo.
Utiliza una función de comparación donde los padres son mayores que sus
hijos.
'''
super().__init__(lambda parent, child: parent < child)

[Link]
© Universidad Alfonso X el Sabio 93
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Clase base MinHeap:

class MinHeap(Heap):
'''
Clase MinHeap para implementar un montículo mínimo, donde cada nodo padre es
menor que sus hijos.
Hereda de la clase Heap.
'''

def __init__(self):
'''
Inicializa un montículo mínimo.
Utiliza una función de comparación donde los padres son menores que sus
hijos.
'''
super().__init__(lambda parent, child: parent > child)

3.10. Colas de prioridad (priority queues)

Una cola de prioridad es una estructura de datos abstracta similar a una cola común o una pila,
pero donde cada elemento tiene una prioridad asignada. Los elementos se sirven según sus
prioridades, en lugar de el orden en que se añadieron a la cola. En general, los elementos con
prioridades más altas se sirven antes que los elementos con prioridades más bajas.

Operaciones básicas
Las operaciones básicas de una cola de prioridad son:

 Insertar (o encolar):
o Añadir un elemento a la cola con una prioridad dada.

 Eliminar (o desencolar):
o Remover y retornar el elemento con la más alta (o más baja, dependiendo de la
implementación) prioridad.

 Peek (o mirar el tope):

o Observar el elemento con la más alta (o más baja) prioridad sin eliminarlo.

 isEmpty:

[Link]
© Universidad Alfonso X el Sabio 94
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

o Comprobar si la cola de prioridad está vacía.

 Tamaño:
o Retornar el número de elementos en la cola.

 Modificar prioridad:
o Cambiar la prioridad de un elemento específico. (Nota: no todas las
implementaciones ofrecen esta operación de manera eficiente).

 Fusionar:
o Combinar dos colas de prioridad en una sola. (Esta operación tampoco es común
en todas las implementaciones, pero algunas estructuras avanzadas la
soportan).
Estas operaciones garantizan que se pueda administrar de manera efectiva una colección de
elementos con prioridades, asegurando que los elementos de mayor prioridad sean procesados
antes que aquellos de menor prioridad.

Usos comunes de las colas de prioridad

Las colas de prioridad son estructuras de datos versátiles con una amplia variedad de
aplicaciones en la informática y en otros campos. Aquí te presento algunos de los usos más
comunes:

 Algoritmos de Camino Mínimo:

o Como el algoritmo de Dijkstra, que utiliza una cola de prioridad para seleccionar
el siguiente nodo más cercano.

 Planificación de Tareas (Scheduling):

o En sistemas operativos, las colas de prioridad se usan para determinar el orden
en el que los procesos o tareas reciben recursos de procesamiento.

 Compresión de Datos:
o En algoritmos de compresión como Huffman, se utiliza una cola de prioridad
para construir el árbol de Huffman.

 Simulaciones:
o Las colas de prioridad son útiles en simulaciones basadas en eventos. Por
ejemplo, en la simulación de un sistema en el que varios eventos ocurren en
diferentes momentos, la cola de prioridad puede ser usada para determinar cuál
es el próximo evento a simular.

[Link]
© Universidad Alfonso X el Sabio 95
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

 Algoritmo de Prim:
o Usado para encontrar el árbol de expansión mínima en un grafo. La cola de
prioridad ayuda a seleccionar el siguiente borde de peso mínimo.

 Algoritmos de Búsqueda:
o En algoritmos como A*, la cola de prioridad se utiliza para explorar el siguiente
nodo más prometedor basado en una función heurística.

 Gestión de Red:
o En la gestión de tráfico de redes, las colas de prioridad pueden ser usadas para
manejar paquetes de datos basados en su prioridad o urgencia.

 Balaustradas de Real-time Systems:

o En sistemas que requieren respuestas en tiempo real, las tareas pueden ser
manejadas basadas en su urgencia o deadline usando colas de prioridad.

 Algoritmos de Fusión:
o Al fusionar múltiples listas ordenadas en una sola lista ordenada.
Estos son solo algunos ejemplos y hay muchas otras aplicaciones de colas de prioridad en la
informática. La capacidad de administrar elementos basados en la prioridad es una necesidad
común en muchos escenarios, y las colas de prioridad ofrecen una forma eficiente de hacerlo.

Ventajas y Desventajas de las Colas de Prioridad

Ventajas Desventajas

Flexibilidad: Permite recuperar y procesar Mayor complejidad computacional en

elementos en función de la prioridad en lugar algunas operaciones: En ciertas
del orden en que fueron agregados. implementaciones, algunas operaciones
pueden ser más lentas que en una cola o pila
simple.

Optimización: Es útil en situaciones donde los Espacio adicional requerido: Al almacenar

datos deben ser procesados de acuerdo a su prioridades, puede requerir más memoria
urgencia o importancia, como en la que una cola o pila simple.
planificación de tareas en un sistema
operativo.

[Link]
© Universidad Alfonso X el Sabio 96
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Utilidad en Algoritmos Específicos: Es Mantenimiento de la estructura: La

esencial para ciertos algoritmos, como el estructura necesita ser actualizada
algoritmo de Dijkstra para encontrar el continuamente para mantener el orden de
camino más corto en un grafo. prioridad.

Implementación
Las colas de prioridad se pueden implementar de diversas maneras, siendo los montículos
(heaps) la estructura de datos más comúnmente utilizada para este fin, debido a su eficiencia.
En particular, el montículo binario (binary heap) es una estructura muy popular para
implementar una cola de prioridad.

En la librería estándar de Python, el módulo heapq provee funciones para convertir listas en
montículos con complejidad O(n) y operaciones de inserción y extracción con complejidad
logarítmica. Sin embargo, hay que tener en cuenta que, aunque este módulo permite simular
una cola de prioridad, no provee una implementación directa de una estructura de cola de
prioridad.

import heapq

class PriorityQueue:
'''
Clase PriorityQueue para implementar una cola de prioridades.

Atributos:
queue (list): Lista para almacenar los elementos de la cola de prioridades.
index (int): Índice secuencial para mantener un orden estable en elementos con
igual prioridad.
'''

def __init__(self):
'''
Inicializa la cola de prioridades.
'''
[Link] = []
[Link] = 0

def push(self, item, priority):

'''
Inserta un elemento en la cola de prioridades con una prioridad dada.

[Link]
© Universidad Alfonso X el Sabio 97
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

:param item: Elemento a insertar en la cola.

:param priority: Prioridad del elemento (un número mayor indica mayor
prioridad).
'''
# El módulo heapq en Python implementa un montículo mínimo por defecto.
# Usamos negación para simular una cola de prioridad máxima.
[Link]([Link], (-priority, [Link], item))
[Link] += 1

def pop(self):
'''
Elimina y devuelve el elemento con la máxima prioridad de la cola.

:return: El elemento con la máxima prioridad.

:raises Exception: Si la cola está vacía.
'''
if [Link]:
_, _, item = [Link]([Link])
return item
raise Exception("Cola vacía")

def peek(self):
'''
Devuelve el elemento con la máxima prioridad sin eliminarlo de la cola.

:return: El elemento con la máxima prioridad.

:raises Exception: Si la cola está vacía.
'''
if [Link]:
_, _, item = [Link][0]
return item
raise Exception("Cola vacía")

def is_empty(self):
'''
Verifica si la cola de prioridades está vacía.

:return: True si la cola está vacía, False en caso contrario.

'''
return not [Link]

# Uso de la cola de prioridad

if __name__ == "__main__":
pq = PriorityQueue()

[Link]
© Universidad Alfonso X el Sabio 98
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

[Link]("Tarea 1", 1)
[Link]("Tarea 2", 4)
[Link]("Tarea 3", 2)

while not pq.is_empty():

print([Link]())

En esta implementación, cada elemento de la cola tiene una prioridad asociada. Cuando los
elementos se agregan a la cola, se les da una prioridad y se encolan en consecuencia. Cuando se
desencolan, el elemento con la mayor prioridad (el número más grande en este caso) se
desencola primero.

La variable index es una técnica utilizada para desempatar en caso de que dos elementos
tengan la misma prioridad. Gracias a ello, se garantiza que los elementos con la misma prioridad
se desencolarán en el orden en que se encolaron.

Ejercicio de repaso
Ejercicio: Gestión de Tareas con Prioridades

Contexto:

Eres el jefe de un equipo de desarrollo de software y tienes varias tareas que asignar a tu equipo.
Dado que algunas tareas son más críticas que otras, decides usar una cola de prioridad para
gestionarlas y asegurarte de que se completen en el orden adecuado.

Instrucciones:

1. Implementa una cola de prioridad para gestionar las tareas.

2. Añade las siguientes tareas a tu cola con las prioridades dadas:
• "Refactorizar código base" con prioridad 3.
• "Implementar nueva característica A" con prioridad 5.
• "Corregir error crítico B" con prioridad 9.
• "Actualizar documentación" con prioridad 2.
• "Revisar y aprobar PRs" con prioridad 4.
3. Desencola las tareas una a una y asígnalas a un miembro del equipo.
4. Muestra el orden en el que se realizarán las tareas según su prioridad.
Preguntas adicionales:

[Link]
© Universidad Alfonso X el Sabio 99
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

1. Si se descubre un error de seguridad crítico mientras las tareas están siendo procesadas,
¿cómo garantizas que este error se corrija antes que las demás tareas?
2. ¿Cómo manejarías la situación si dos tareas tienen la misma prioridad?
3. Imagina que la cola de prioridad es utilizada en un entorno donde las tareas y sus
prioridades cambian constantemente. ¿Qué desafíos podrías enfrentar y cómo podrías
adaptar tu implementación para manejarlos?
Salida esperada:

Deberías desencolar las tareas en el siguiente orden:

1. "Corregir error crítico B"

2. "Implementar nueva característica A"
3. "Revisar y aprobar PRs"
4. "Refactorizar código base"
5. "Actualizar documentación"
Rúbrica de Evaluación:

1. Implementación correcta de la cola de prioridad: 40 puntos.

2. Añadir tareas con prioridades correctamente: 20 puntos.
3. Desencolar y asignar tareas en orden de prioridad: 20 puntos.
4. Respuestas correctas y lógicas a las preguntas adicionales: 20 puntos.
Este ejercicio te ayudará a comprender cómo funciona una cola de prioridad en un escenario del
mundo real y cómo puede ser útil para gestionar tareas con diferentes niveles de urgencia o
importancia.

[Link]
© Universidad Alfonso X el Sabio 100
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

3.11. Conjuntos (sets)

Los conjuntos (o "sets" en inglés) son colecciones no ordenadas de elementos únicos. Es decir,
en un conjunto, cada elemento aparece una sola vez. Los conjuntos no tienen un orden
específico y no se pueden acceder por índices.
En la mayoría de los lenguajes de programación, incluido Python, existen estructuras de datos
que implementan la idea matemática de un conjunto.

Operaciones básicas
Los conjuntos, como estructuras de datos, tienen varias operaciones básicas que reflejan las
operaciones matemáticas tradicionales de los conjuntos, además de algunas operaciones
específicas relacionadas con su implementación en programación. A continuación, vemos las
operaciones más comunes:

 Inserción: Agrega un elemento al conjunto. Si el elemento ya existe en el

conjunto, no se realiza ninguna modificación.

 Eliminación: Elimina un elemento específico del conjunto. Si el elemento

no está presente, la operación puede generar un error o simplemente no
hacer nada, dependiendo del lenguaje o la implementación.

 Pertenencia: Comprueba si un elemento específico está presente en el

conjunto.

 Tamaño: Devuelve el número de elementos en el conjunto.

 Unión: Combina dos conjuntos en un nuevo conjunto que contiene todos
los elementos de ambos conjuntos (sin duplicados).

 Intersección: Crea un nuevo conjunto que contiene todos los elementos

que están presentes en ambos conjuntos.

 Diferencia: Crea un nuevo conjunto que contiene todos los elementos del
primer conjunto que no están presentes en el segundo conjunto.

 Subconjunto: Comprueba si un conjunto es un subconjunto de otro, es

decir, si todos los elementos del primer conjunto están presentes en el
segundo conjunto.

 Conjunto vacío: Crea un nuevo conjunto sin elementos.

 Igualdad: Verifica si dos conjuntos contienen los mismos elementos.

[Link]
© Universidad Alfonso X el Sabio 101
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

 Diferencia simétrica: Devuelve un conjunto con todos los elementos que

están en uno de los conjuntos, pero no en ambos.

 Clonación/Copia: Crea una copia del conjunto.

Estas operaciones básicas permiten manipular y consultar conjuntos en programación de la
misma manera que se haría en matemáticas, pero con la ventaja adicional de poder trabajar con
grandes cantidades de datos y combinar conjuntos con otras estructuras de datos y algoritmos.

Usos comunes de los conjuntos

Los conjuntos, o "sets", en programación y en ciencias de la computación tienen diversos usos
comunes debido a sus propiedades únicas (como la no repetición de elementos). Algunos de los
usos más habituales incluyen:

 Eliminación de duplicados: Dado que un conjunto no permite

elementos duplicados, es una herramienta natural para filtrar listas o
colecciones y eliminar repetidos.

 Verificación de pertenencia: Determinar si un elemento ya está en un

conjunto es una operación muy eficiente, más que en listas o arrays.

 Operaciones matemáticas: Los conjuntos pueden usarse para realizar

operaciones matemáticas tradicionales entre conjuntos, como unión,
intersección y diferencia.

 Representación de grupos o categorías: En ciertas aplicaciones, es

necesario representar un grupo o categoría de objetos (por ejemplo,
usuarios que pertenecen a un grupo específico).

 Problemas de grafos: En algoritmos relacionados con grafos, los

conjuntos pueden usarse para representar, por ejemplo, conjuntos de
nodos visitados.

 Cacheo y memoización: En problemas de optimización, un conjunto

puede usarse para rastrear soluciones ya calculadas o estados ya visitados.

 Implementación de otros algoritmos y estructuras de datos: En

estructuras más complejas, como las Tablas Hash o grafos, los conjuntos
pueden ser útiles como estructura auxiliar.

 Problemas de búsqueda y coincidencia: Por ejemplo, en ciertos

problemas donde es necesario determinar las coincidencias entre dos
conjuntos de datos.

[Link]
© Universidad Alfonso X el Sabio 102
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

 Verificar subconjuntos: Para determinar rápidamente si un conjunto es

subconjunto de otro.

 Desarrollo de juegos: Para rastrear conjuntos de objetos, como

conjuntos de jugadores en línea en una determinada sala de juego.

 Análisis de datos y minería: En el análisis de grandes conjuntos de

datos, se pueden utilizar conjuntos para realizar operaciones de
comparación y agrupación de datos.

En general, los conjuntos son útiles en cualquier situación en la que sea importante garantizar
la unicidad de los elementos y cuando se realizan operaciones de conjunto tradicionales de
manera regular. La eficiencia de las operaciones de conjunto en ciertas implementaciones
también hace que sean preferibles a las listas en ciertos escenarios.

Ventajas y desventajas

Ventajas Desventajas

Eliminación de duplicados: Los conjuntos No ordenados: No se puede acceder a los

automáticamente eliminan duplicados, lo elementos de un conjunto por un índice o
cual es útil para operaciones donde sólo se posición.
quieren elementos únicos.

Operaciones matemáticas: Es fácil realizar No admite elementos mutables: En algunos

operaciones matemáticas de conjuntos como lenguajes (como Python), los conjuntos no
unión, intersección, diferencia, etc. pueden contener elementos mutables como
listas o diccionarios.

Búsqueda eficiente: Verificar si un elemento Mayor consumo de memoria: A veces, los

está en un conjunto es generalmente rápido. conjuntos pueden consumir más memoria
que otras estructuras de datos, como las
listas, debido a las estructuras internas
necesarias para mantener la unicidad y la
eficiencia en las operaciones.

No tiene restricciones de tipo: Un conjunto

puede contener cualquier tipo de datos:
números, cadenas, tuplas, etc.

Implementación

[Link]
© Universidad Alfonso X el Sabio 103
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

En Python, los conjuntos se pueden crear utilizando llaves {} (similar a los diccionarios, pero sin
claves y valores) o usando la función set().

mi_conjunto = {1, 2, 3, 4, 5}
otro_conjunto = set([1, 2, 2, 3, 4]) # Esto crea un conjunto con elementos {1, 2, 3,
4}

Las operaciones comunes con conjuntos incluyen la adición y eliminación de elementos, y las
operaciones matemáticas de conjuntos como mencionado anteriormente.

Aunque Python ya dispone de esta estructura de datos es interesante que veamos cuál sería una
posible implementación de este tipo de estructura:

class CustomSet:
'''
Clase CustomSet para implementar una estructura de conjunto personalizada.

Atributos:
elements (dict): Diccionario para almacenar los elementos del conjunto.
Los valores son irrelevantes, se utiliza principalmente la
clave.
'''

def __init__(self):
'''
Inicializa un conjunto vacío.
'''
[Link] = {}

def add(self, value):

'''
Agrega un valor al conjunto.

:param value: Valor a agregar al conjunto.

'''
# Añade el valor como clave en el diccionario. El valor asociado no es
relevante.
if value not in [Link]:
[Link][value] = True

def remove(self, value):

'''

[Link]
© Universidad Alfonso X el Sabio 104
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Elimina un valor del conjunto.

:param value: Valor a eliminar del conjunto.

'''
# Elimina el valor del diccionario si existe.
if value in [Link]:
del [Link][value]

def contains(self, value):

'''
Verifica si un valor está en el conjunto.

:param value: Valor a verificar.

:return: True si el valor está en el conjunto, False en caso contrario.
'''
# Verifica la presencia del valor en el diccionario.
return value in [Link]

def size(self):
'''
Devuelve el tamaño del conjunto.

:return: Número de elementos en el conjunto.

'''
# Devuelve la cantidad de claves en el diccionario.
return len([Link])

def union(self, other_set):

'''
Devuelve la unión con otro conjunto.

:param other_set: Otro objeto CustomSet para realizar la unión.

:return: Un nuevo CustomSet que es la unión del conjunto actual y other_set.
'''
# Crea un nuevo conjunto y añade elementos de ambos conjuntos.
result = CustomSet()
for elem in [Link]:
[Link](elem)
for elem in other_set.elements:
[Link](elem)
return result

def intersection(self, other_set):

'''

[Link]
© Universidad Alfonso X el Sabio 105
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

Devuelve la intersección con otro conjunto.

:param other_set: Otro objeto CustomSet para realizar la intersección.

:return: Un nuevo CustomSet que es la intersección del conjunto actual y
other_set.
'''
# Crea un nuevo conjunto y añade solo los elementos comunes a ambos
conjuntos.
result = CustomSet()
for elem in [Link]:
if elem in other_set.elements:
[Link](elem)
return result

def difference(self, other_set):

'''
Devuelve la diferencia con otro conjunto.

:param other_set: Otro objeto CustomSet para realizar la diferencia.

:return: Un nuevo CustomSet que contiene elementos que están en el conjunto
actual pero no en other_set.
'''
# Crea un nuevo conjunto y añade elementos que están solo en el conjunto
actual.
result = CustomSet()
for elem in [Link]:
if elem not in other_set.elements:
[Link](elem)
return result

def __str__(self):
'''
Representación en cadena del conjunto.

:return: Una representación en cadena del conjunto, mostrando sus elementos.

'''
# Devuelve una cadena con todos los elementos del conjunto, separados por
comas.
return "{" + ", ".join(map(str, [Link]())) + "}"

Este CustomSet es una implementación simplificada y está basada en un diccionario para

obtener la eficiencia de operaciones básicas. Hay muchas maneras de optimizar y expandir esta

[Link]
© Universidad Alfonso X el Sabio 106
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

implementación básica, pero espero que esta implementación nos da una idea clara de cómo se
puede construir desde cero.

Ejercicio de repaso
Ejercicio: Administración de un Club de Lectura

Eres el encargado de administrar un club de lectura en tu localidad. Para ello, decides utilizar
conjuntos o sets para llevar un control sobre los libros que cada miembro ha leído.

Escenario:

1. Cada miembro del club de lectura tiene una lista de libros que ha leído.
2. Cada libro tiene un título único.
3. Los miembros suelen intercambiar recomendaciones entre ellos sobre qué libros leer a
continuación.
Tareas a realizar:

1. Crear conjuntos para al menos 3 miembros diferentes, con los libros que han leído.
2. Encuentra qué libros han leído todos los miembros (intersección de todos los
conjuntos).
3. Encuentra qué libros ha leído el primer miembro pero no los otros (diferencia).
4. Recomienda a un miembro los libros que otros dos miembros han leído pero él no
(diferencia y unión).
5. Añade un nuevo libro leído a la lista de uno de los miembros.
6. Elimina un libro leído de la lista de uno de los miembros.
7. Encuentra y muestra qué libros son únicos para cada miembro.
Datos de Muestra:

• Jose ha leído: "Orgullo y prejuicio", "1984", "Un mundo feliz", "Cien años de soledad".
• María ha leído: "Orgullo y prejuicio", "Moby Dick", "La Odisea", "Cien años de soledad",
"Los juegos del hambre".
• Miriam ha leído: "1984", "Un mundo feliz", "La Odisea", "Los juegos del hambre".
Usa los métodos del set para llevar a cabo las tareas solicitadas y muestra los resultados.

Este ejercicio te ayudará a practicar las operaciones básicas de conjuntos como unión,
intersección y diferencia en un escenario práctico y real.

[Link]
© Universidad Alfonso X el Sabio 107
 Unidad 1: Estructuras dinámicas de datos
Algoritmos y Estructuras de Datos

4. Bibliografía
• Aho, A. V., Hopcroft, J. E., & Ullman, J. D. (1983). Data Structures and Algorithms.
Addison-Wesley.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms
(3ra ed.). MIT Press.
• Dasgupta, S., Papadimitriou, C. H., & Vazirani, U. V. (2006). Algorithms. McGraw-Hill
Higher Education.
• Goodrich, M. T., & Tamassia, R. (2014). Data Structures and Algorithms in Java (6ta ed.).
Wiley.
• Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2013). Data Structures and
Algorithms in Python. Wiley.
• Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson Education.
• Knuth, D. E. (1968-2011). The Art of Computer Programming (Vols. 1-4). Addison-
Wesley.
• Mehlhorn, K., & Sanders, P. (2008). Algorithms and Data Structures: The Basic Toolbox.
Springer.
• Nadal Farré, M. (2022). Estructuras de Datos y Algoritmos. [Título del libro o editorial no
especificado].
• Python Software Foundation. (2023). Python 3 Documentation. Recuperado de
[Link]
• Sedgewick, R. (1998). Algorithms in C++, Parts 1-4: Fundamentals, Data Structures,
Sorting, Searching (3ra ed.). Addison-Wesley Professional.
• Sedgewick, R., & Wayne, K. (2011). Algorithms (4ta ed.). Addison-Wesley Professional.
• Skiena, S. S. (2008). The Algorithm Design Manual (2da ed.). Springer.
• Wirth, N. (1976). Algorithms + Data Structures = Programs. Prentice-Hall.

[Link]
© Universidad Alfonso X el Sabio 108
GRACIAS

[Link]