DAA - Metode Sisipkan
Untuk menyisipkan elemen di heap, elemen baru awalnya ditambahkan ke akhir heap sebagai elemen terakhir dari array.
Setelah memasukkan elemen ini, properti heap mungkin dilanggar, oleh karena itu properti heap diperbaiki dengan membandingkan elemen yang ditambahkan dengan induknya dan memindahkan elemen yang ditambahkan ke atas satu tingkat, bertukar posisi dengan induknya. Proses ini disebutpercolation up.
Perbandingan diulang sampai induk lebih besar dari atau sama dengan elemen perkolasi.
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)
Analisis
Awalnya, elemen ditambahkan di akhir larik. Jika melanggar properti heap, elemen tersebut akan ditukar dengan induknya. Tinggi pohon itulog n. Maksimumlog n jumlah operasi perlu dilakukan.
Oleh karena itu, kompleksitas fungsi ini O(log n).
Contoh
Mari kita pertimbangkan max-heap, seperti yang ditunjukkan di bawah ini, di mana elemen baru 5 perlu ditambahkan.
Awalnya, 55 akan ditambahkan di akhir larik ini.
Setelah penyisipan, ini melanggar properti heap. Karenanya, elemen perlu ditukar dengan induknya. Setelah ditukar, heap terlihat seperti berikut.
Sekali lagi, elemen tersebut melanggar properti heap. Oleh karena itu, ia ditukar dengan induknya.
Sekarang, kita harus berhenti.