際際滷

際際滷Share a Scribd company logo

Struktur data 08 (heap)

Download as PPT, PDF
Sunarya Marwah
Sunarya Marwah
1 of 24
Downloaded 34 times
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah BAGIAN VIIBAGIAN VII
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap Bila ada suatu urutan data di dalam array: R[0] , R[1], R[3], R[4], . . . ,R[n]R[0] , R[1], R[3], R[4], . . . ,R[n] sedemikian rupa sehingga: R[i] < r[2i + 1] dan R[i] < R[2i + 2]R[i] < r[2i + 1] dan R[i] < R[2i + 2] atau R[i] > r[2i + 1] dan R[i] > R[2i + 2]R[i] > r[2i + 1] dan R[i] > R[2i + 2] maka data tersebut berada dalam struktur HEAP.
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap Ada dua macam struktur Heap:Ada dua macam struktur Heap: a.a.Min Heap : R[0] berisi data terkecilMin Heap : R[0] berisi data terkecil b.b.Max Heap: R[0] berisi data terbesarMax Heap: R[0] berisi data terbesar Contoh: No. R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap 1. 10 15 22 31 34 45 48 Y 2. 10 15 45 22 31 34 48 T 3. 48 31 45 22 15 34 10 Y
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap Tabel diatas akan lebih mudah dilihat sebagai Heap atauTabel diatas akan lebih mudah dilihat sebagai Heap atau bukan, bila digambarkan dalam bentuk Binary treebukan, bila digambarkan dalam bentuk Binary tree. No. 1: Min HeapNo. 1: Min Heap 10 15 3431 22 4845 R[0] R[1] R[2] R[3] R[4] R[5] R[6]
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 10 15 3122 45 4834 R[0] R[1] R[2] R[3] R[4] R[5] R[6] No. 2: Bukan Heap
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 48 31 1522 45 1034 R[0] R[1] R[2] R[3] R[4] R[5] R[6] No. 3: Max Heap
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 10 15 3122 45 4834 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Membangun Heap Buat batas yang melingkupi data yang telah dianggap sebagai Heap. Semua leaf dianggap telah memenuhi sarat heap.
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 10 15 3122 45 4834 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Membangun Heap Perluas batas kearah atas. Test R[2], ternyata R[2] harus ditukar dengan R[5]
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 10 15 3122 34 4845 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Membangun Heap Perluas batas kearah kiri. Test R[1], ternyata R[1] sudah heap
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 10 15 3122 34 4845 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Membangun Heap Perluas batas kearah atas. Test R[0], ternyata R[0] sudah heap
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 10 15 3122 34 4845 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Membangun Heap SelesaiSelesai
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Heap SortHeap Sort 10 15 3122 34 4845 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Tukar R[0] dengan R[6]Tukar R[0] dengan R[6]
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 48 15 3122 34 1045 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort R[6] keluar dari heapR[6] keluar dari heap
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 15 48 3122 34 1045 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Atur kembali heap, tukar R[0] dengan R[1]Atur kembali heap, tukar R[0] dengan R[1]
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 15 22 3148 34 1045 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Atur kembali heap, tukar R[1] dengan R[3]Atur kembali heap, tukar R[1] dengan R[3]
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 15 22 3148 34 1045 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Tukar R[0] dengan R[5]Tukar R[0] dengan R[5]
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 45 22 3148 34 1015 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort R[5] keluar dari heapR[5] keluar dari heap
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 22 45 3148 34 1015 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Atur kembali heap, tukar R[0] dengan R[2]Atur kembali heap, tukar R[0] dengan R[2]
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 22 31 4548 34 1015 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Atur kembali heap, tukar R[1] dengan R[4]Atur kembali heap, tukar R[1] dengan R[4]
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 22 31 4548 34 1015 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Tukar R[0] dengan R[4]Tukar R[0] dengan R[4]
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 45 31 2248 34 1015 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort R[4] keluar dari heap.R[4] keluar dari heap. Demikian seterusnya hingga R[1] keluar dari heapDemikian seterusnya hingga R[1] keluar dari heap
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 48 45 2231 34 1015 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Selesai, didapat urutan secaraSelesai, didapat urutan secara descendingdescending
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort Algoritma Heap sortAlgoritma Heap sort 1.1. Membangun heap.Membangun heap. 2.2. Tukar root dengan elemen terakhir heap.Tukar root dengan elemen terakhir heap. 3.3. Ukuran heap berkurang satu.Ukuran heap berkurang satu. 4.4. Atur kembali heap.Atur kembali heap. 5.5. Ulangi langkah 2 s/d 4 hingga heapsize = 1.Ulangi langkah 2 s/d 4 hingga heapsize = 1. 6.6. Selesai.Selesai.
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort Latihan.Latihan. 1.1. Lakukan heapsort untuk data:Lakukan heapsort untuk data: 75 23 16 46 32 58 80 61 97 4975 23 16 46 32 58 80 61 97 49 secarasecara ascendingascending.. 2. Lakukan heapsort untuk data:2. Lakukan heapsort untuk data: 16 23 32 46 49 58 61 75 83 85 91 9416 23 32 46 49 58 61 75 83 85 91 94 secarasecara descendingdescending..

More Related Content

Struktur data 08 (heap)

  • 1. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah BAGIAN VIIBAGIAN VII
  • 2. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap Bila ada suatu urutan data di dalam array: R[0] , R[1], R[3], R[4], . . . ,R[n]R[0] , R[1], R[3], R[4], . . . ,R[n] sedemikian rupa sehingga: R[i] < r[2i + 1] dan R[i] < R[2i + 2]R[i] < r[2i + 1] dan R[i] < R[2i + 2] atau R[i] > r[2i + 1] dan R[i] > R[2i + 2]R[i] > r[2i + 1] dan R[i] > R[2i + 2] maka data tersebut berada dalam struktur HEAP.
  • 3. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap Ada dua macam struktur Heap:Ada dua macam struktur Heap: a.a.Min Heap : R[0] berisi data terkecilMin Heap : R[0] berisi data terkecil b.b.Max Heap: R[0] berisi data terbesarMax Heap: R[0] berisi data terbesar Contoh: No. R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap 1. 10 15 22 31 34 45 48 Y 2. 10 15 45 22 31 34 48 T 3. 48 31 45 22 15 34 10 Y
  • 4. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap Tabel diatas akan lebih mudah dilihat sebagai Heap atauTabel diatas akan lebih mudah dilihat sebagai Heap atau bukan, bila digambarkan dalam bentuk Binary treebukan, bila digambarkan dalam bentuk Binary tree. No. 1: Min HeapNo. 1: Min Heap 10 15 3431 22 4845 R[0] R[1] R[2] R[3] R[4] R[5] R[6]
  • 5. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 10 15 3122 45 4834 R[0] R[1] R[2] R[3] R[4] R[5] R[6] No. 2: Bukan Heap
  • 6. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 48 31 1522 45 1034 R[0] R[1] R[2] R[3] R[4] R[5] R[6] No. 3: Max Heap
  • 7. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 10 15 3122 45 4834 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Membangun Heap Buat batas yang melingkupi data yang telah dianggap sebagai Heap. Semua leaf dianggap telah memenuhi sarat heap.
  • 8. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 10 15 3122 45 4834 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Membangun Heap Perluas batas kearah atas. Test R[2], ternyata R[2] harus ditukar dengan R[5]
  • 9. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 10 15 3122 34 4845 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Membangun Heap Perluas batas kearah kiri. Test R[1], ternyata R[1] sudah heap
  • 10. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 10 15 3122 34 4845 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Membangun Heap Perluas batas kearah atas. Test R[0], ternyata R[0] sudah heap
  • 11. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah HeapHeap 10 15 3122 34 4845 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Membangun Heap SelesaiSelesai
  • 12. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Heap SortHeap Sort 10 15 3122 34 4845 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Tukar R[0] dengan R[6]Tukar R[0] dengan R[6]
  • 13. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 48 15 3122 34 1045 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort R[6] keluar dari heapR[6] keluar dari heap
  • 14. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 15 48 3122 34 1045 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Atur kembali heap, tukar R[0] dengan R[1]Atur kembali heap, tukar R[0] dengan R[1]
  • 15. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 15 22 3148 34 1045 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Atur kembali heap, tukar R[1] dengan R[3]Atur kembali heap, tukar R[1] dengan R[3]
  • 16. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 15 22 3148 34 1045 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Tukar R[0] dengan R[5]Tukar R[0] dengan R[5]
  • 17. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 45 22 3148 34 1015 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort R[5] keluar dari heapR[5] keluar dari heap
  • 18. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 22 45 3148 34 1015 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Atur kembali heap, tukar R[0] dengan R[2]Atur kembali heap, tukar R[0] dengan R[2]
  • 19. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 22 31 4548 34 1015 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Atur kembali heap, tukar R[1] dengan R[4]Atur kembali heap, tukar R[1] dengan R[4]
  • 20. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 22 31 4548 34 1015 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Tukar R[0] dengan R[4]Tukar R[0] dengan R[4]
  • 21. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 45 31 2248 34 1015 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort R[4] keluar dari heap.R[4] keluar dari heap. Demikian seterusnya hingga R[1] keluar dari heapDemikian seterusnya hingga R[1] keluar dari heap
  • 22. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort 48 45 2231 34 1015 R[0] R[1] R[2] R[3] R[4] R[5] R[6] Heap sort Selesai, didapat urutan secaraSelesai, didapat urutan secara descendingdescending
  • 23. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort Algoritma Heap sortAlgoritma Heap sort 1.1. Membangun heap.Membangun heap. 2.2. Tukar root dengan elemen terakhir heap.Tukar root dengan elemen terakhir heap. 3.3. Ukuran heap berkurang satu.Ukuran heap berkurang satu. 4.4. Atur kembali heap.Atur kembali heap. 5.5. Ulangi langkah 2 s/d 4 hingga heapsize = 1.Ulangi langkah 2 s/d 4 hingga heapsize = 1. 6.6. Selesai.Selesai.
  • 24. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah Sorting; Heap SortSorting; Heap Sort Latihan.Latihan. 1.1. Lakukan heapsort untuk data:Lakukan heapsort untuk data: 75 23 16 46 32 58 80 61 97 4975 23 16 46 32 58 80 61 97 49 secarasecara ascendingascending.. 2. Lakukan heapsort untuk data:2. Lakukan heapsort untuk data: 16 23 32 46 49 58 61 75 83 85 91 9416 23 32 46 49 58 61 75 83 85 91 94 secarasecara descendingdescending..