Slides TD Parcial2-121-130

Vista previa del material en texto

Max Heap: Eliminación (1)
Para eliminar el máximo:
1. intercambiamos la raiz con la última hoja,
2. eliminamos la última hoja,
3. vamos bajando de nivel el elemento que quedo en la raíz mientra sea
menor que algún hijo.
(si es menor que ambos hijos lo bajamos en dirección al hijo más grande)
17
Max Heap: Eliminación (2)
Para eliminar el máximo:
1. intercambiamos la raiz con la última hoja,
2. eliminamos la última hoja,
3. vamos bajando de nivel el elemento que quedo en la raíz mientra sea
menor que algún hijo.
(si es menor que ambos hijos lo bajamos en dirección al hijo más grande)
18
Max Heap: Eliminación (3)
Para eliminar el máximo:
1. intercambiamos la raiz con la última hoja,
2. eliminamos la última hoja,
3. vamos bajando de nivel el elemento que quedo en la raíz mientra sea
menor que algún hijo.
(si es menor que ambos hijos lo bajamos en dirección al hijo más grande)
19
Max Heap: Eliminación (4)
Para eliminar el máximo:
1. intercambiamos la raiz con la última hoja,
2. eliminamos la última hoja,
3. vamos bajando de nivel el elemento que quedo en la raíz mientra sea
menor que algún hijo.
(si es menor que ambos hijos lo bajamos en dirección al hijo más grande)
20
Arbol binario: Max Heap en vector
▶ Como el árbol binario heap es izquierdista, se puede representar con
un vector.
▶ Se almacena cada nivel de arriba hacia abajo y de izquierda a
derecha.
21
Arbol binario: Max Heap en vector
Notar que:
▶ La raíz está en v[0].
▶ Los hijos del nodo v[i] están en v[2i + 1] y v[2i + 2].
▶ El padre del nodo v[i] está en v[(i - 1)/2].
22
Max Heap � Vector
1 vector<int> _heap;
2 // Rep: - _heap[i] >= _heap[2*i+1] and _heap[i] >= _heap[2*i+2]
3 // para todo 0 <= i < (_heap.size()-1)/2
4 }
5
6 int padre(int pos) {
7 return (pos-1)/2;
8 }
9 int hijo_izq(int pos) {
10 return 2*pos+1;
11 }
12 int hijo_der(int pos) {
13 return 2*pos+2;
14 }
Para el caso del heap esta representación de árbol binario es más
simple de implementar.
23
Heap: bajar
1 // hace descender por el heap al elemento en la ubicación pos
2 void bajar(vector<int>& heap, int pos) {
3 int pos_bajar = max_hijo(heap, pos);
4 if (pos_bajar != pos) {
5 std::swap(heap[pos], heap[pos_bajar]);
6 bajar(heap, pos_bajar);
7 }
8 }
9 void max_hijo(vector<int>& heap, int pos) {
10 inr ret = pos; // default: raiz
11 if (2*pos+1 < heap.size() &&
12 heap[ret] < heap[2*pos+1])
13 ret = 2*pos+1; // elijo izquierdo
14 if (2*pos+2 < heap.size() &&
15 heap[ret] < heap[2*pos+2]) {
16 ret = 2*pos+2; // elijo derecho
17 return ret;
18 }
Ejercicio: escribir el algoritmo para subir(vector<int>& heap, int pos) 24
Max Heap: insertar y eliminar
1 void insertar(int n, vector<int> & _heap) {
2 _heap.push_back(n);
3 subir(_heap,_heap.size()-1);
4 }
5
6 void eliminar(vector<int> & _heap) {
7 _heap[0] = _heap[_heap.size()-1];
8 _heap.pop_back();
9 bajar(_heap,0);
10 }
25
Motivación Árbol Binario de Búsqueda
Problema: Necesito almacenar elementos distintos ordenados, y
agregar/quitar/buscar de manera e�ciente:
▶ Agregar en O(log n)
▶ Quitar en O(log n)
▶ Buscar en O(log n)
Idea: almacenarlos de manera conveniente en un arbol binario.
▶ El elemento de la raíz es mayor que los de la izquierda y menor
que los de la derecha.
▶ Mantengo la altura cercana a log n
27