DAA - Método de inserción

Para insertar un elemento en un montón, el nuevo elemento se agrega inicialmente al final del montón como último elemento de la matriz.

Después de insertar este elemento, la propiedad del montón se puede violar, por lo tanto, la propiedad del montón se repara comparando el elemento agregado con su padre y moviendo el elemento agregado hacia arriba un nivel, intercambiando posiciones con el padre. Este proceso se llamapercolation up.

La comparación se repite hasta que el padre es mayor o igual que el elemento de filtración.

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

Análisis

Inicialmente, se agrega un elemento al final de la matriz. Si viola la propiedad del montón, el elemento se intercambia con su padre. La altura del árbol eslog n. Máximolog n número de operaciones necesarias.

Por tanto, la complejidad de esta función es O(log n).

Ejemplo

Consideremos un montón máximo, como se muestra a continuación, donde es necesario agregar un nuevo elemento 5.

Inicialmente, se agregarán 55 al final de esta matriz.

Después de la inserción, viola la propiedad del montón. Por lo tanto, el elemento debe intercambiarse con su padre. Después del intercambio, el montón tiene el siguiente aspecto.

Una vez más, el elemento viola la propiedad de montón. Por lo tanto, se intercambia con su padre.

Ahora tenemos que parar.