Heaps (2016)

Apunte Español
Universidad Universidad Autónoma de Barcelona (UAB)
Grado Ingeniería Informática - 2º curso
Asignatura Laboratori de Programació
Año del apunte 2016
Páginas 1
Fecha de subida 27/06/2017
Descargas 0
Subido por

Vista previa del texto

HEAPS LISTA DE PRIORIDADES (PRIORITY QUEQUE) Estructura que consiste en un conjunto de elementos, cada uno de ellos asociados a una clave con las siguientes operaciones: - insert: inserta un elemento ‘x’ en el conjunto.
- Max, min: devuelve el elemento con la clave más grande, pequeña.
- ExtractMax, extractMin: devuelve el elemento con la clave más grande, pequeña y lo elimina del conjunto.
- IncreaseKey,decreaseKey: incrementa, decrementa la clave de un elemento en una cantidad determinada que siempre será igual o mayor, menor que la existente.
Binary Heap Árbol binario casi completo con propiedades: 1) La clave de un nodo es menor o igual que la de sus hijos 2) Altura de un nodo ‘i’: número de enlaces del camino más largo que va desde el nodo ‘i’ hasta una hoja.
3) Altura de un heap de n nodos: árbol casi completo => complejidad log(n) Operaciones: o BuildMax: creación de un heap a partir de un array => O(n) o MaxHeapify: corrección incumplimiento propiedad de claves => O(log n) o Insert: O(log n) o ExtractMax: O(log n) o IncreaseKey: O(log n) o HeapSort: ordena un array “in place” => O(n log n) ...