Makalah Heap Pada Struktur Data
Heap Pada Struktur Data
KATA PENGANTAR
Makalah yang berjudul “Heap Pada Struktur Data”menjelaskan tentang pengertian
heap, skema-skema pada heap, dan juga operasi-operasi dasar pada heap. Kami ingin
mengucapkan terima kasih kepada semua pihak yang telah membantu dan mendukung dalam
penyelesaian makalah ini sehingga makalah inibisa selesai tepat pada waktunya.
Kami menyadari bahwa dalam makalah ini masih banyak kekurangan yang perlu
diperbaiki.Kami mohon maaf jika di dalam makalah ini di temukan banyak kesalahan. Maka dari
itu, kritik dan saran dari pembaca yang bersifat membangun sangat kami harapkan demi
menyempurnakan makalah yang di buat selanjutnya.
Kami berharap semoga makalah ini bisa berguna dan bermanfaat bagi pembaca dan dari
semua kalangan termasuk teman-teman semua.
Singaraja,Desember2011
Penulis
BAB I
PENDAHULUAN
1.1 Latar Belakang
Struktur data heap adalah sebuah objek array yang dapat divisualisasikan dengan
sebuah complete binary tree. Hubungan antara elemen dari array dan node pada pohon
merupakan hubungan korespondensi satu satu. Pohon diisi secara penuh pada semua level,
kecuali kemungkinan terkecil, dimana diisi dari kiri sampai ke sebuah titik.
Semua node dari heap juga memenuhi relasi bahwa nilai kunci pada setiap node minimal sama
besar dengan nilai dari node anaknya.
Struktur data dari algoritma Heap adalah sebuah pohon biner sempurna yang memenuhi
properti heap. Node akar (root node) memiliki data terbesar atau terkecil yang terdapat pada
pohon. Demikian juga pada subtree-nya, dimana node induk (parent) memiliki data yang paling
besar atau paling kecil dibandingkan dengan data pada kedua anaknya (child node sebelah kiri
atau sebelah kanan).
BAB II
PEMBAHASAN
Pengertian Struktur Data Heap
struktur data heap adalah sebuah objek array yang dapat dengan mudah divisualisasikan
sebagai complete tree. Ada korespondensi satu ke satu diantara elemen array dan node
dari tree. tree itu benar-benar penuh pada semua tingkatan kecuali mungkin yang
terendah, yang diisi dari kiri sampai titik tertentu. Semua node dari heap juga memenuhi
hubungan bahwa nilai kunci pada setiap node pada kurangnya sama besar dengan nilai
pada anak-anaknya.
Ini dapat dilihat sebagai sebuah pohon biner dengan dua kendala tambahan:
a. Bentuk property : pohon itu adalah complete binary tree , yaitu semua tingkat tree,
kecuali mungkin yang terakhir (paling dalam) sepenuhnya diisi, dan, jika tingkat terakhir
tree itu tidak lengkap, maka node pada tingkat itu diisi dari kiri ke kanan.
b. Sifat heap: setiap node lebih besar dari atau sama dengan masing-masing anak sesuai
dengan perbandingan predikat yang ditetapkan untuk struktur data.
Jenis heap :
Min Heap: setiap elemen node adalah lebih kecil daripada children nya.
Ini menunjukan bahwa elemen terkecil terletak pada root dari tree.
Unsur terbesar adalah terletak di suatu tempat di salah satu node leaves.
Max Heap: setiap elemen node adalah lebih besar daripada children nya.
Karena urutan sibling dalam heap tidak ditentukan oleh sifat heap, dua node tunggal
anak-anak bisa secara bebas dipertukarkan kecuali melakukan hal itu melanggar properti
bentuk
Heap operations :
1. Insert
Untuk menambahkan sebuah element ke HEAP kita harus melakukan operasi up-heap
(juga dikenal sebagai bubble-up, percolate-up, sift-up, heapify-up, atau cascade-up) untuk
mengembalikan sifat heap. Kita dapat melakukan ini dalam O (log n) time, menggunakan
binary heap, dengan mengikuti algoritma ini:
1. Tambahkan elemen pada level bawah heap.
2. Bandingkan elemen yg baru ditambahkan dengan parentnya, jika mereka berada di
urutan yang benar, berhenti.
3. Jika tidak, swap elemen dengan parent dan kembali ke langkah sebelumnya.
Kita melakukan ini maksimum sekali untuk masing-masing tingkat di ketinggian tree,
yang adalah O (log n). Namun, karena sekitar 50% dari elemen adalah leaves dan 75%
berada di dua level di bawah, kemungkinan bahwa unsur baru yang akan dimasukkan
hanya akan berpindah beberapa level ke atas untuk mempertahankan heap. Dengan
demikian, binary heap mendukung insertion rata-rata dalam waktu yang konsta, O (1).
Misalkan kita memiliki heap
dan kita ingin menambahkan nomor 15 ke heap. Pertama-tama kita tempatkan 15 di
posisi yg ditandai dengan X. Namun, sifat heap dilanggar karena 15 lebih besar dari 8,
jadi kita perlu menukar 15 dan 8. Jadi, kita memiliki heap yg tampak sebagai berikut
setelah swap pertama:
Namun sifat heap masih dilanggar karena 15 lebih besar dari 11, jadi kita perlu swap lagi:
Ini adalah max-heap yang valid. Tidak perlu untuk memeriksa children setelah ini.
Sebelum kita menempatkan 15 pada X, tumpukan ini valid, yang berarti 11 lebih besar
dari 5. Jika 15 lebih besar dari 11, dan 11 lebih besar dari 5, maka 15 harus lebih besar
dari 5, karena dari relasi transitif.
2. remove
Prosedur untuk men-delete akar dari tumpukan dan restorasi disebut down-heap (juga
dikenal sebagai bubble-down, percolate-down, sift-down, heapify-down, or cascade-
down)
Ganti root heap dengan elemen terakhir pada level terakhir.
Bandingkan root baru dengan childrennya, jika mereka berada di urutan yang benar,
berhenti.
Jika tidak, swap unsur dengan salah satu childrennya dan kembali ke langkah
sebelumnya. (Swap dengan children yang lebih kecil di min-heap dan children yang lebih
besar di max-heap.)
Jadi, jika kita memiliki max heap-sama seperti sebelumnya, kita menghapus 11 dan
menggantinya dengan 4.
Sekarang sifat heap dilanggar karena 8 lebih besar dari 4. Dalam hal ini, menukar dua
elemen 4 dan 8, sudah cukup untuk mengembalikan sifat heap dan kita tidak perlu swap
elemen lebih lanjut:
Simpul di bawah node yang bergerak di-swap dengan semakin besar children dalam
sebuah max-heap (dalam min-heap akan bertukar dengan children nya yang lebih kecil),
sampai memenuhi sifat heap di posisi baru
BAB III
PENUTUP
1. KESIMPULAN
A. heap adalah sebuah objek array yang dapat dengan mudah divisualisasikan sebagai
complete tree.
B. Jenis heap :
Min Heap: setiap elemen node adalah lebih kecil daripada children nya.
Ini menunjukan bahwa elemen terkecil terletak pada root dari tree.
Unsur terbesar adalah terletak di suatu tempat di salah satu node leaves.
Max Heap: setiap elemen node adalah lebih besar daripada children nya.
Karena urutan sibling dalam heap tidak ditentukan oleh sifat heap, dua node tunggal
anak-anak bisa secara bebas dipertukarkan kecuali melakukan hal itu melanggar properti
bentuk
DAFTAR FUSTAKA
o http://dasar2ilmukomputer.blogspot.com/2008/02/definisi-t- heap.html
o http://pengertian-definisi.blogspot.com/2012/01/pengertian- heap.html
o http://pengertian-definisi.blogspot.com/2011/11/manfaat- heap.html
http://www.irwantoshut.net/klasifikasi_jenis_tanah.html
http://belajargeo-erinz.comoj.com
http://green-fruit.blogspot.com
KATA PENGANTAR
Makalah yang berjudul “Heap Pada Struktur Data”menjelaskan tentang pengertian
heap, skema-skema pada heap, dan juga operasi-operasi dasar pada heap. Kami ingin
mengucapkan terima kasih kepada semua pihak yang telah membantu dan mendukung dalam
penyelesaian makalah ini sehingga makalah inibisa selesai tepat pada waktunya.
Kami menyadari bahwa dalam makalah ini masih banyak kekurangan yang perlu
diperbaiki.Kami mohon maaf jika di dalam makalah ini di temukan banyak kesalahan. Maka dari
itu, kritik dan saran dari pembaca yang bersifat membangun sangat kami harapkan demi
menyempurnakan makalah yang di buat selanjutnya.
Kami berharap semoga makalah ini bisa berguna dan bermanfaat bagi pembaca dan dari
semua kalangan termasuk teman-teman semua.
Singaraja,Desember2011
Penulis
BAB I
PENDAHULUAN
1.1 Latar Belakang
Struktur data heap adalah sebuah objek array yang dapat divisualisasikan dengan
sebuah complete binary tree. Hubungan antara elemen dari array dan node pada pohon
merupakan hubungan korespondensi satu satu. Pohon diisi secara penuh pada semua level,
kecuali kemungkinan terkecil, dimana diisi dari kiri sampai ke sebuah titik.
Semua node dari heap juga memenuhi relasi bahwa nilai kunci pada setiap node minimal sama
besar dengan nilai dari node anaknya.
Struktur data dari algoritma Heap adalah sebuah pohon biner sempurna yang memenuhi
properti heap. Node akar (root node) memiliki data terbesar atau terkecil yang terdapat pada
pohon. Demikian juga pada subtree-nya, dimana node induk (parent) memiliki data yang paling
besar atau paling kecil dibandingkan dengan data pada kedua anaknya (child node sebelah kiri
atau sebelah kanan).
BAB II
PEMBAHASAN
Pengertian Struktur Data Heap
struktur data heap adalah sebuah objek array yang dapat dengan mudah divisualisasikan
sebagai complete tree. Ada korespondensi satu ke satu diantara elemen array dan node
dari tree. tree itu benar-benar penuh pada semua tingkatan kecuali mungkin yang
terendah, yang diisi dari kiri sampai titik tertentu. Semua node dari heap juga memenuhi
hubungan bahwa nilai kunci pada setiap node pada kurangnya sama besar dengan nilai
pada anak-anaknya.
Ini dapat dilihat sebagai sebuah pohon biner dengan dua kendala tambahan:
a. Bentuk property : pohon itu adalah complete binary tree , yaitu semua tingkat tree,
kecuali mungkin yang terakhir (paling dalam) sepenuhnya diisi, dan, jika tingkat terakhir
tree itu tidak lengkap, maka node pada tingkat itu diisi dari kiri ke kanan.
b. Sifat heap: setiap node lebih besar dari atau sama dengan masing-masing anak sesuai
dengan perbandingan predikat yang ditetapkan untuk struktur data.
Jenis heap :
Min Heap: setiap elemen node adalah lebih kecil daripada children nya.
Ini menunjukan bahwa elemen terkecil terletak pada root dari tree.
Unsur terbesar adalah terletak di suatu tempat di salah satu node leaves.
Max Heap: setiap elemen node adalah lebih besar daripada children nya.
Karena urutan sibling dalam heap tidak ditentukan oleh sifat heap, dua node tunggal
anak-anak bisa secara bebas dipertukarkan kecuali melakukan hal itu melanggar properti
bentuk
Heap operations :
1. Insert
Untuk menambahkan sebuah element ke HEAP kita harus melakukan operasi up-heap
(juga dikenal sebagai bubble-up, percolate-up, sift-up, heapify-up, atau cascade-up) untuk
mengembalikan sifat heap. Kita dapat melakukan ini dalam O (log n) time, menggunakan
binary heap, dengan mengikuti algoritma ini:
1. Tambahkan elemen pada level bawah heap.
2. Bandingkan elemen yg baru ditambahkan dengan parentnya, jika mereka berada di
urutan yang benar, berhenti.
3. Jika tidak, swap elemen dengan parent dan kembali ke langkah sebelumnya.
Kita melakukan ini maksimum sekali untuk masing-masing tingkat di ketinggian tree,
yang adalah O (log n). Namun, karena sekitar 50% dari elemen adalah leaves dan 75%
berada di dua level di bawah, kemungkinan bahwa unsur baru yang akan dimasukkan
hanya akan berpindah beberapa level ke atas untuk mempertahankan heap. Dengan
demikian, binary heap mendukung insertion rata-rata dalam waktu yang konsta, O (1).
Misalkan kita memiliki heap
dan kita ingin menambahkan nomor 15 ke heap. Pertama-tama kita tempatkan 15 di
posisi yg ditandai dengan X. Namun, sifat heap dilanggar karena 15 lebih besar dari 8,
jadi kita perlu menukar 15 dan 8. Jadi, kita memiliki heap yg tampak sebagai berikut
setelah swap pertama:
Namun sifat heap masih dilanggar karena 15 lebih besar dari 11, jadi kita perlu swap lagi:
Ini adalah max-heap yang valid. Tidak perlu untuk memeriksa children setelah ini.
Sebelum kita menempatkan 15 pada X, tumpukan ini valid, yang berarti 11 lebih besar
dari 5. Jika 15 lebih besar dari 11, dan 11 lebih besar dari 5, maka 15 harus lebih besar
dari 5, karena dari relasi transitif.
2. remove
Prosedur untuk men-delete akar dari tumpukan dan restorasi disebut down-heap (juga
dikenal sebagai bubble-down, percolate-down, sift-down, heapify-down, or cascade-
down)
Ganti root heap dengan elemen terakhir pada level terakhir.
Bandingkan root baru dengan childrennya, jika mereka berada di urutan yang benar,
berhenti.
Jika tidak, swap unsur dengan salah satu childrennya dan kembali ke langkah
sebelumnya. (Swap dengan children yang lebih kecil di min-heap dan children yang lebih
besar di max-heap.)
Jadi, jika kita memiliki max heap-sama seperti sebelumnya, kita menghapus 11 dan
menggantinya dengan 4.
Sekarang sifat heap dilanggar karena 8 lebih besar dari 4. Dalam hal ini, menukar dua
elemen 4 dan 8, sudah cukup untuk mengembalikan sifat heap dan kita tidak perlu swap
elemen lebih lanjut:
Simpul di bawah node yang bergerak di-swap dengan semakin besar children dalam
sebuah max-heap (dalam min-heap akan bertukar dengan children nya yang lebih kecil),
sampai memenuhi sifat heap di posisi baru
BAB III
PENUTUP
1. KESIMPULAN
A. heap adalah sebuah objek array yang dapat dengan mudah divisualisasikan sebagai
complete tree.
B. Jenis heap :
Min Heap: setiap elemen node adalah lebih kecil daripada children nya.
Ini menunjukan bahwa elemen terkecil terletak pada root dari tree.
Unsur terbesar adalah terletak di suatu tempat di salah satu node leaves.
Max Heap: setiap elemen node adalah lebih besar daripada children nya.
Karena urutan sibling dalam heap tidak ditentukan oleh sifat heap, dua node tunggal
anak-anak bisa secara bebas dipertukarkan kecuali melakukan hal itu melanggar properti
bentuk
DAFTAR FUSTAKA
o http://dasar2ilmukomputer.blogspot.com/2008/02/definisi-t- heap.html
o http://pengertian-definisi.blogspot.com/2012/01/pengertian- heap.html
o http://pengertian-definisi.blogspot.com/2011/11/manfaat- heap.html
http://www.irwantoshut.net/klasifikasi_jenis_tanah.html
http://belajargeo-erinz.comoj.com
http://green-fruit.blogspot.com
Leave a Comment