Repaso de conceptos básicos: montículos binarios (binary heaps)

Clase: 18/09/2012 - 25/09/2012

Lee los temas 9.1 a 9.3 del libro "Estructuras de datos, algoritmos y programación orientada a objetos" (1998) de G. L. Heileman.

Mira estas transparencias de A. Castellanos sobre colas de prioridad para la asignatura IS13, desde la página 21.

También puedes consultar los temas 6.1 a 6.4 del libro "Data structures and algorithm analysis in C++" (Third ed., 2006) de M. A. Weiss.

Montículos izquierdistas (leftist heaps)

Clase: 25/09/2012 - 02/10/2012

Seguiremos el tema 9.2.1 del libro "Fundamentals of Data Structures in C++" (Second ed., 2007) de E. Horowitz, S. Sahni y D. Mehta.

Resuelve estos ejercicios:

Ejercicio 1.b del examen de enero 2011.
Ejercicio 3 del examen de septiembre 2011 [PUNTUABLE 1 DESDE 02/10/2012 HASTA 18/10/2012].
Ejercicio 2.b del examen de septiembre 2009.
Ejercicios 3.b y 3.c del examen de septiembre 2008.

Montículos binomiales (binomial heaps)

Clase: 02/10/2012 - 16/10/2012 (el 09/10/2012 es festivo)

Seguiremos los temas 12.1 y 12.2.3 del libro "Estructuras de datos, algoritmos y programación orientada a objetos" (1998) de G. L. Heileman.

Mira estas transparencias de la Universidad de Princeton.

Prueba esta animación.

Resuelve estos ejercicios:

Ejercicio 1.a del examen de enero 2011.
Ejercicio 2.b del examen de septiembre 2010.
Ejercicio 1.1.a del examen de enero 2008.

Montículos binomiales perezosos (lazy binomial heaps) y montículos de Fibonacci (Fibonacci heaps)

Clase: 16/10/2012 - 23/10/2012

Seguiremos los temas 12.3.2 y 12.3.3 del libro "Estructuras de datos, algoritmos y programación orientada a objetos" (1998) de G. L. Heileman.

El tema 19 del libro "Introduction to Algorithms" (Third ed., 2009) de T. H. Cormen, Ch. E. Leiserson, R. L. Rivest y C. Stein también es muy recomendable.

Veremos las demostraciones de costes en el tema sobre análisis amortizado.

Mira estas transparencias de la Universidad de Princeton.

Prueba esta animación.

Resuelve estos ejercicios:

Ejercicios 1.1.b y 1.1.c del examen de enero 2008.
Ejercicio 2.c del examen de septiembre 2009.
Ejercicio 2 del examen de enero 2009.
Ejercicio 4 del examen de enero 2011 [PUNTUABLE 2 DESDE 23/10/2012 HASTA 08/11/2012].
Ejercicio 5 del examen de septiembre 2009.

Colas de prioridad de doble fin: montículos de intervalos (interval heaps)

Clase: 23/10/2012

Este apartado se presentará muy brevemente y será objeto de trabajo no presencial, teniendo en cuenta que es de fácil comprensión siguiendo la bibliografía.

Lee el tema 9.7 del libro "Fundamentals of Data Structures in C++" (Second ed., 2007) de E. Horowitz et al. y acude a tutorías para resolver las dudas que tengas.

Resuelve estos ejercicios:

Ejercicios 1, 2 y 3 de ese tema.
Ejercicio 2 del examen de septiembre 2008 [PUNTUABLE 3 DESDE 06/11/2012 HASTA 22/11/2012].

En cursos pasados las estructuras de datos que hemos estudiado para implementar colas de prioridad de doble fin han sido los montículos min-max y los deaps, siguiendo los temas 9.1 y 9.2 del libro "Fundamentals of Data Structures in C++" (First ed., 1995) de E. Horowitz et al. Los ejercicios que veas sobre ellos en los exámenes pasados no serán materia de examen este curso.