My first Magazine pemrograman-kompetitif-dasar | Page 124

10 Struktur Data NonLinear
Gambar 10.17: Contoh penomoran indeks complete binary tree pada array .
Dengan logika yang serupa, orang tua dari node ke-i adalah node ke-b i−1
2 c. Apabila Anda
memutuskan untuk menggunakan array one-based, maka rumusnya menjadi:
• Anak kiri: 2i.
• Anak kanan: 2i + 1.
• Orang tua: bi/2c
Karena panjang array dapat bertambah atau berkurang, diperlukan array yang ukurannya
dinamis. Namun, pada contoh ini, kita akan menggunakan array berukuran statis dan sebuah
variabel yang menyatakan ukuran array saat ini. Ukuran array statis ini bisa dibuat sebesar
banyaknya operasi push paling banyak yang mungkin dilakukan, yang misalnya dinyatakan sebagai
maxSize. Algoritma 53 menunjukkan prosedur untuk melakukan inisialisasi pada heap .
Algoritma 53 Inisialisasi pada heap , arrHeap dan size merupakan variabel global.
arrHeap ← new integer[maxSize]
2: procedure INITIALIZE H EAP ()
3:
size ← 0
4: end procedure
1:
. Buat array arrHeap berukuran maxSize
. Variabel yang menunjukkan ukuran array saat ini.
Untuk memudahkan penulisan kode, mari definisikan fungsi pembantu yang ditunjukkan pada
Algoritma 54. Secara berturut-turut, fungsi tersebut adalah fungsi untuk mencari indeks orang
tua, anak kiri, maupun anak kanan dari suatu node . Algoritma 55 sampai dengan Algoritma 57
menunjukkan implementasi untuk operasi push , pop , dan top .
114