ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo

Struktur data 10 (min max heap)

•Download as PPTX, PDF•
•
Sunarya Marwah
Sunarya Marwah
1 of 35
Downloaded 49 times
min-MAX Heap By Sunarya D. Marwah Copyright@Sunarya D. Marwah
Min-Max Heap adalah struktur binary tree, dimana suatu node x berada di level min maka semua node dibawahnya, nilainya harus lebih besar dari nilai node x tersebut, dan bila node x berada di level max, maka seluruh node dibawahnya harus lebih kecil dari nilai node x tersebut. Copyright@Sunarya D. Marwah Min-MAX Heap
Contoh Min-Max Heap Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max
Hasse Diagram Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 40 Min Max
Insert ke Min-Max Heap Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Maxx
x = 10; Insert(x) Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max10 = Tukar x< 40
Insert(10) Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 10 Min Min Max Max40 x< 15
Insert(10) Copyright@Sunarya D. Marwah Min-MAX Heap 10 65 80 20 30 35 50 55 60 45 70 75 25 15 Min Min Max Max40
x = 85; Insert(85) Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max85 x > 40
x = 85; Insert(85) Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max85 x > 80
x = 85; Insert(85) Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 85 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max80
Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 Min
Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 20 Min Max
Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 20 30 Min Max
Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 20 30 40 Min Min Max
Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 40 30 20 Min Min Max
Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 40 30 20 50 Min Min Max
Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 50 30 20 40 Min Min Max
Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 50 30 20 40 60 Min Min Max
Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 50 60 20 40 30 Min Min Max
Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 50 60 20 40 30 Min Min Max 70
Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 50 70 20 40 30 Min Min Max 60
Delete Delete dari Min-Max Heap terdiri dari: 1. DeleteMin 2. DeleteMax DeleteMin langsung mengambil elemen paling puncak yaitu level Min teratas , sedangkan DeleteMax harus memilih elemen terbesar di level Max teratas, baru melakukan DeleteMax. Copyright@Sunarya D. Marwah Min-MAX Heap
Delete Baik DeleteMin maupun DeleteMax, pengganti node yang dihapus diambil dari node dengan elemen terkecil dari anak-anak dan cucu- cucunya, kemudian elemen yang kosong diisi dari elemen terakhir, kemudian lakukan reheap. Contoh delete akan menggunakan konstruksi heap yang ada di slide nomor 10. Copyright@Sunarya D. Marwah Min-MAX Heap
DeleteMin Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 85 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max80
DeleteMin Copyright@Sunarya D. Marwah Min-MAX Heap 65 85 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max80
Mencari elemen dengan nilai terkecil Heap[k] dari anak-anak dan cucu-cucunya, kemudian mengisi elemen puncak yang telah kosong. Copyright@Sunarya D. Marwah Min-MAX Heap 65 85 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max80
Copyright@Sunarya D. Marwah Min-MAX Heap 20 65 85 30 35 50 55 60 45 70 75 25 40 Min Min Max Max80
Copyright@Sunarya D. Marwah Min-MAX Heap 20 65 85 80 30 35 50 55 60 45 70 75 25 40 Min Min Max Max
Copyright@Sunarya D. Marwah Min-MAX Heap 20 80 85 65 30 35 50 55 60 45 70 75 25 40 Min Min Max Max
Copyright@Sunarya D. Marwah Min-MAX Heap 20 80 85 35 30 65 50 55 60 45 70 75 25 40 Min Min Max Max
DeleteMax Pilih elemen terbesar di level max teratas, max = 85 Copyright@Sunarya D. Marwah Min-MAX Heap 20 80 85 35 30 65 50 55 60 45 70 75 25 40 Min Min Max Max
DeleteMax Pilih elemen terbesar dari anak-anak dan cucu-cucunya. Copyright@Sunarya D. Marwah Min-MAX Heap 20 80 35 30 65 50 55 60 45 70 75 25 40 Min Min Max Max
Copyright@Sunarya D. Marwah Min-MAX Heap 20 80 75 35 30 65 50 55 60 45 70 25 40 Min Min Max Max
Kelebihan dari struktur Min-Max Heap dibanding dengan Heap biasa, adalah DeleteMin dan DeleteMax bisa dilakukan dalam satu struktur. Copyright@Sunarya D. Marwah Min-MAX Heap

More Related Content

Struktur data 10 (min max heap)

  • 1. min-MAX Heap By Sunarya D. Marwah Copyright@Sunarya D. Marwah
  • 2. Min-Max Heap adalah struktur binary tree, dimana suatu node x berada di level min maka semua node dibawahnya, nilainya harus lebih besar dari nilai node x tersebut, dan bila node x berada di level max, maka seluruh node dibawahnya harus lebih kecil dari nilai node x tersebut. Copyright@Sunarya D. Marwah Min-MAX Heap
  • 3. Contoh Min-Max Heap Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max
  • 4. Hasse Diagram Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 40 Min Max
  • 5. Insert ke Min-Max Heap Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Maxx
  • 6. x = 10; Insert(x) Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max10 = Tukar x< 40
  • 7. Insert(10) Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 10 Min Min Max Max40 x< 15
  • 8. Insert(10) Copyright@Sunarya D. Marwah Min-MAX Heap 10 65 80 20 30 35 50 55 60 45 70 75 25 15 Min Min Max Max40
  • 9. x = 85; Insert(85) Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max85 x > 40
  • 10. x = 85; Insert(85) Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 80 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max85 x > 80
  • 11. x = 85; Insert(85) Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 85 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max80
  • 12. Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 Min
  • 13. Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 20 Min Max
  • 14. Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 20 30 Min Max
  • 15. Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 20 30 40 Min Min Max
  • 16. Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 40 30 20 Min Min Max
  • 17. Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 40 30 20 50 Min Min Max
  • 18. Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 50 30 20 40 Min Min Max
  • 19. Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 50 30 20 40 60 Min Min Max
  • 20. Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 50 60 20 40 30 Min Min Max
  • 21. Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 50 60 20 40 30 Min Min Max 70
  • 22. Insert: +10 +20 +30 +40 +50 +60 +70 Copyright@Sunarya D. Marwah Min-MAX Heap 10 50 70 20 40 30 Min Min Max 60
  • 23. Delete Delete dari Min-Max Heap terdiri dari: 1. DeleteMin 2. DeleteMax DeleteMin langsung mengambil elemen paling puncak yaitu level Min teratas , sedangkan DeleteMax harus memilih elemen terbesar di level Max teratas, baru melakukan DeleteMax. Copyright@Sunarya D. Marwah Min-MAX Heap
  • 24. Delete Baik DeleteMin maupun DeleteMax, pengganti node yang dihapus diambil dari node dengan elemen terkecil dari anak-anak dan cucu- cucunya, kemudian elemen yang kosong diisi dari elemen terakhir, kemudian lakukan reheap. Contoh delete akan menggunakan konstruksi heap yang ada di slide nomor 10. Copyright@Sunarya D. Marwah Min-MAX Heap
  • 25. DeleteMin Copyright@Sunarya D. Marwah Min-MAX Heap 15 65 85 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max80
  • 26. DeleteMin Copyright@Sunarya D. Marwah Min-MAX Heap 65 85 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max80
  • 27. Mencari elemen dengan nilai terkecil Heap[k] dari anak-anak dan cucu-cucunya, kemudian mengisi elemen puncak yang telah kosong. Copyright@Sunarya D. Marwah Min-MAX Heap 65 85 20 30 35 50 55 60 45 70 75 25 40 Min Min Max Max80
  • 28. Copyright@Sunarya D. Marwah Min-MAX Heap 20 65 85 30 35 50 55 60 45 70 75 25 40 Min Min Max Max80
  • 29. Copyright@Sunarya D. Marwah Min-MAX Heap 20 65 85 80 30 35 50 55 60 45 70 75 25 40 Min Min Max Max
  • 30. Copyright@Sunarya D. Marwah Min-MAX Heap 20 80 85 65 30 35 50 55 60 45 70 75 25 40 Min Min Max Max
  • 31. Copyright@Sunarya D. Marwah Min-MAX Heap 20 80 85 35 30 65 50 55 60 45 70 75 25 40 Min Min Max Max
  • 32. DeleteMax Pilih elemen terbesar di level max teratas, max = 85 Copyright@Sunarya D. Marwah Min-MAX Heap 20 80 85 35 30 65 50 55 60 45 70 75 25 40 Min Min Max Max
  • 33. DeleteMax Pilih elemen terbesar dari anak-anak dan cucu-cucunya. Copyright@Sunarya D. Marwah Min-MAX Heap 20 80 35 30 65 50 55 60 45 70 75 25 40 Min Min Max Max
  • 34. Copyright@Sunarya D. Marwah Min-MAX Heap 20 80 75 35 30 65 50 55 60 45 70 25 40 Min Min Max Max
  • 35. Kelebihan dari struktur Min-Max Heap dibanding dengan Heap biasa, adalah DeleteMin dan DeleteMax bisa dilakukan dalam satu struktur. Copyright@Sunarya D. Marwah Min-MAX Heap