DAA - metoda wstawiania

Aby wstawić element do sterty, nowy element jest początkowo dołączany na końcu sterty jako ostatni element tablicy.

Po wstawieniu tego elementu, właściwość sterty może zostać naruszona, stąd właściwość sterty jest naprawiana poprzez porównanie dodanego elementu z jego rodzicem i przeniesienie dodanego elementu na wyższy poziom, zamieniając się pozycjami z elementem nadrzędnym. Ten proces nazywa siępercolation up.

Porównanie jest powtarzane, aż element nadrzędny jest większy lub równy elementowi przesączającemu.

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)

Analiza

Początkowo element jest dodawany na końcu tablicy. Jeśli narusza właściwość sterty, element jest wymieniany ze swoim rodzicem. Wysokość drzewa tolog n. Maksymalnylog n liczba operacji do wykonania.

Stąd złożoność tej funkcji O(log n).

Przykład

Rozważmy maksymalny stos, jak pokazano poniżej, w którym należy dodać nowy element 5.

Początkowo na końcu tej tablicy zostanie dodane 55.

Po wstawieniu narusza właściwość sterty. Dlatego element musi zamienić się ze swoim rodzicem. Po zamianie sterta wygląda następująco.

Ponownie element narusza właściwość sterty. W związku z tym jest zamieniany z rodzicem.

Teraz musimy się zatrzymać.