Algoritmo Insertar
Cuando se llega a un árbol vacío se crea el nodo en el
puntero que se pasa como parámetro por referencia, de esta manera los nuevos
enlaces mantienen la coherencia. Si el elemento a insertar ya existe entonces
no se hace nada.
void insertar(tarbol **a, int elem)
{
if (*a == NULL) {
*a = (arbol *)
malloc(sizeof(arbol));
(*a)->clave
= elem;
(*a)->izq = (*a)->der = NULL;
}
else if ((*a)->clave <
elem) insertar(&(*a)->der, elem);
else if ((*a)->clave >
elem) insertar(&(*a)->izq, elem);
}
Llamada recursiva a Heapify para sus i’s subárboles, si
no cumplen con la propiedad del heap
Heap-size[A] à 10
A[2], i = 2 no cumple con la
propiedad de un heap (MAX-HEAP)
Tiempo de ejecución de
heapify
En un subárbol de tamaño n,
con raíz en el nodo i
Θ(1), relación fija entre
A[i], A[LEFT(i)], A[RIGHT(i)] más
Tiempo de ejecución de
HEAPIFY en un subárbol con raíz en uno de los hijos de i
Tamaño de los subárboles de
los hijos es a lo más 2n/3
T(n) ≤ T(2n/3) Θ(1)
Por el caso 2 del método
maestro
T(n) = O(lgn)
Alternativa
Caracterizar
tiempo de ejecución de HEAPIFY sobre un nodo de altura h como: O(h)
Uso de heapify para
construir el heap
Los elementos A[(floor(n/2)
+ 1) … n] son hojas del árbol
Orden
en que se procesan los nodos garantiza que los subárboles con raíz en los hijos
del nodo i son heaps antes de que HEAPIFY se ejecute en dicho nodo
Algoritmo BuildHeap
No hay comentarios:
Publicar un comentario