DAA - Método de Inserção

Para inserir um elemento em um heap, o novo elemento é inicialmente anexado ao final do heap como o último elemento da matriz.

Depois de inserir este elemento, a propriedade heap pode ser violada, portanto, a propriedade heap é reparada comparando o elemento adicionado com seu pai e movendo o elemento adicionado um nível acima, trocando posições com o pai. Este processo é chamadopercolation up.

A comparação é repetida até que o pai seja maior ou igual ao elemento percolador.

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álise

Inicialmente, um elemento está sendo adicionado ao final da matriz. Se ele violar a propriedade heap, o elemento será trocado por seu pai. A altura da árvore élog n. Máximolog n número de operações precisa ser executado.

Portanto, a complexidade desta função é O(log n).

Exemplo

Vamos considerar um heap máximo, conforme mostrado abaixo, onde um novo elemento 5 precisa ser adicionado.

Inicialmente, 55 serão adicionados ao final desta matriz.

Após a inserção, ele viola a propriedade heap. Portanto, o elemento precisa ser trocado por seu pai. Após a troca, o heap se parece com o seguinte.

Novamente, o elemento viola a propriedade de heap. Portanto, ele é trocado por seu pai.

Agora, temos que parar.