Algoritmos INSERTAR y HEAPIFY

INSERCIÓN

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);
}

ALGORITMO HEAPIFY

 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