Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

INFO088_2018_09

No description
by

Erick Araya

on 22 July 2018

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of INFO088_2018_09

Heap: Estructura de Datos
Heap: Estructura de Datos
Punteros y Memoria Dinámica
Heap: Estructura de Datos

ESTRUCTURAS DINÁMICAS PARTE 6
Apunte 09
Taller de Ingeniería: Estructura de Datos y Algoritmos
Organización de la memoria asignada a una aplicación en C o C++:
Código completo:
Punteros y Memoria Dinámica
Punteros y Memoria Dinámica
Heap: Estructura de Datos
Para esta clase se verá sólo el "Max-Heap".
Heap: Estructura de Datos
Un hijo del nivel-2 (99) es mayor que el padre del nivel-1(45). Debe intercambiarse. Sin embargo, esto provoca una nueva violación: ahora el hijo del nivel-3 (63) es mayor que el padre del nivel-2 (45). Deben intercambiarse. El árbol final queda:
Heap: Estructura de Datos
El main(), que imprime primero el arreglo original y luego el max-heap almacenado en el arreglo, se muestra a continuación:
Para manejar memoria dinámica, en C:
Heap: Estructura de Datos
En la medida que se van ejecutando las funciones, primero cuadrado() y luego cuadradoDeSuma(), éstas irán dejando el stack:
Luego, main() llamará a cout que aparecerá en el stack...
Punteros y Memoria Dinámica
Heap: Estructura de Datos
Una heap es una estructura de datos especial, basada en un árbol. Su requerimiento básico es que el valor de un nodo debe ser >= (ó <=) que los valores de sus hijos (propiedad de una heap)
Definición
Creación de un heap
Dado un arreglo de valores al azar, se debe buscar una forma de convertir este arreglo en un max-heap. El procedimiento es el que sigue:
Como se ve, en el nivel-4 un hijo (99) es mayor que su padre. Deben intercambiarse.
Consideremos el siguiente arreglo desordenado:
En el nivel-3, de izquierda a derecha, debe hacerse dos intercambios de hijos con sus padres del nivel-2
Es un árbol binario completo (o lleno, con la posible excepción del último nivel)...
Las propiedades de las heaps binarias son:
Dejaremos el cuarto segmento (heap) pendiente por unos momentos
Punteros y Memoria Dinámica
Cuando se ejecuta este programa veremos que pasa en memoria. Se ha definido en naranja el segmento para las variables globales y en verde para el stack o pila.
Inserción en un Max-Heap
Suponga que el max heap tiene n-nodos. Una vez insertado un nodo, tendrá n+1 nodos, pero el árbol resultante debe ser un árbol binario completo con n-nodos.
Ejemplos de inserción se muestran a continuación (note donde comienza la inserción del nuevo nodo):
En el caso cuando se quiere insertar x = 16, note que ocurre una violación a la regla (12 es el padre de un hijo de mayor valor). En esos casos se realiza un "swap" (intercambio) entre los valores
Como son 9 elementos, hay que crear una estructura de árbol con 9 nodos.
Memoria para las instrucciones que necesitan ejecutarse
Variables que permanecen mientras dura la ejecución del programa
Llamado de funciones y variables locales (al interior de las funciones) que "viven" mientras se ejecuta la función.
Explicaremos con un programa cómo se usan los tres segmentos cuando éste se ejecuta.
Al ejecutarse el programa:
main()
a,b
total
Stack-frame
Técnica de administración de memoria usada en algunos lenguajes para generar y eliminar variables temporales. Su tamaño se define durante compilación
CDS()
Cuando en main() se invoca cuadradoDeSuma(), CDS(), se crea otro stack-frame con el nombre de la función y las variables
x,y,z
Cuando se ejecuta CDS(), invoca a cuadrado(), cuad(), creándose otro stack frame.
cuad()
x
Note que al tope del stack queda cuadrado(), el cual se ejecuta, mientras las otras funciones quedan en espera, hasta que cuadrado() finaliza.
Note también que total es una variable global, por lo que puede ser usada en cualquier momento
main()
a,b
total
CDS()
x,y,z
cuad()
x
main()
a,b
total
CDS()
x,y,z
main()
a,b
total
cout
Y cuando cout finaliza, abandona el stack
main()
a,b
total
Finalmente, main() y la variable global.
Todas las variables y funciones definirán su tamaño durante compilación. El stack es de tamaño fijo, esto es, si ocurre un llamado recursivo, puede que ocurra un "stack overflow", indicando que el espacio asignado al stack está lleno y no puede ingresar en él otro stack-frame.
La "heap", otra organización de memoria, no tiene tamaño fijo, como el stack anterior. Puede crecer según los requerimientos de la aplicación , pero su implementación dependerá del sistema operativo, de la capacidad del compilador, o del lenguaje durante el tiempo de ejecución.
Cuando se usa heap, es porque se permite asignación dinámica de memoria, Definámosla de esta forma:
La heap que se muestra NO TIENE que ver con la estructura de datos que se verá más tarde (a diferencia del stack)
malloc
calloc
realloc
free
Funciones
Para manejar memoria dinámica, en C++ (ya las conocemos):
new
delete
Operadores
También en C++ se pueden usar las funciones anteriores, aún cuando un programador de C++ evita usarlas.
Heap Binaria
... donde cada nodo satisface alguna de las siguientes propiedades:
Si B es hijo de A, entonces en un
max-heap
, key(A) >= key(B)
Si B es hijo de A, entonces en un
min-heap
, key(A) <= key(B)
Como una heap se define como un árbol binario completo, sus elementos pueden ser almacenados de forma secuencial en un arreglo.
En relación a la ubicación de los elementos en el arreglo, si uno de ellos se encuentra en la posición i (i > 0), entonces su hijo izquierdo quedará almacenado en la posición 2i y su hijo derecho en 2i+1 (algunos autores usan 2i+1 y 2i+2 para las posiciones de los hijos del nodo padre, que se encuentra en 2i). Por el contrario, el padre de i estará almacenado en la posición i/2 (entero)
La totalidad de los niveles del árbol binario deben encontrarse completos, excepto el último nivel
Para la siguiente max-heap:
La organización de los datos en memoria será
Otra propiedad de las heaps es que todas sus hojas deben estar a niveles h o h-1 (h = altura del árbol)
Existen tres tipos de heaps: heaps binarias (cuyas propiedades ya hemos adelantado), heaps binomiales heaps de Fibonacci
Tipos
Inserta x
x = 8
x = 16
array<int, N> numeros = {45,36,54,27,63,72,61,18,99};
Se debe distribuir este arreglo en un árbol binario completo, de la siguiente manera:
En esta estructura, se irá distribuyendo los elementos del arreglo de izquierda a derecha, desde la raíz hacia abajo
El siguiente paso es revisar, desde el nivel más alto (nivel-4, en este caso), si hay alguna violación del max-head.
Y queda, hasta ahora:
El nuevo arreglo, max-heap, queda:
99 63 72 36 45 54 61 18 27
La salida será:
Note que, cuando hay que hacer un intercambio de valores, se utiliza la función swap()
Observe también que la función construyeHeap() es recursiva y va por niveles
La función creaHeap() se encarga de recorrer el árbol del más alto nivel a la raíz.
Heap: Estructura de Datos
Para validar el algoritmo anterior, se usará la Standard Template Library (STL), una colección de estructuras de datos genéricas y algoritmos escritos en C++.
La STL provee una colección de estructuras de datos "contenedoras" y algoritmos genéricos que se pueden utilizar con éstas.
Se dice que una estructura de datos es
contenedora
si puede contener
instancias
(réplicas)
de otras estructuras de datos.
Usar en sus algoritmos la STL permite:
Utilizar la misma librería en todos los proyectos, disminuyendo el tiempo de aprendizaje necesario cuando el programador cambia de proyecto.
Incrementar la productividad (algoritmos reutilizables)
Crear aplicaciones de modo rápido, dado que se construyen a partir de algoritmos eficientes
Incrementa la legibilidad del código (más fácil de mantener)
Entre otros componentes, la STL incluye una serie de algoritmos, entre los que se incluyen los de ordenamiento, búsqueda y algoritmos numéricos. Se usará el algoritmo
make_heap().

Heap: Estructura de Datos
El algoritmo con la STL es:
Al compilar y ejecutar este programa con los mismos datos que el código anterior, los resultados son idénticos
Full transcript