DAA - Yöntem Ekle

Bir öbeğe bir öğe eklemek için, yeni öğe başlangıçta dizinin son öğesi olarak yığının sonuna eklenir.

Bu eleman eklendikten sonra, öbek özelliği ihlal edilebilir, dolayısıyla, öbek özelliği, eklenen eleman ile üst öğe karşılaştırılarak ve eklenen eleman bir seviye yukarı hareket ettirilerek, üst öğe ile konum değiştirilerek onarılır. Bu sürece denirpercolation up.

Karşılaştırma, ebeveyn süzülen elemandan daha büyük veya ona eşit olana kadar tekrar edilir.

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)

Analiz

Başlangıçta, dizinin sonuna bir öğe ekleniyor. Öbek özelliğini ihlal ederse, öğe üstüyle değiştirilir. Ağacın yüksekliğilog n. Maksimumlog n yapılması gereken işlem sayısı.

Dolayısıyla, bu işlevin karmaşıklığı O(log n).

Misal

Aşağıda gösterildiği gibi, yeni bir element 5'in eklenmesi gereken bir maksimum yığın düşünelim.

Başlangıçta bu dizinin sonuna 55 eklenecektir.

Eklendikten sonra, yığın özelliğini ihlal ediyor. Bu nedenle, öğenin üst öğesi ile değişmesi gerekir. Takas işleminden sonra, yığın aşağıdaki gibi görünür.

Yine, öğe öbek özelliğini ihlal ediyor. Bu nedenle, ebeveyni ile değiştirilir.

Şimdi durmalıyız.