struktur data 10 (min max heap)
Post on 02-Jul-2015
535 Views
Preview:
TRANSCRIPT
min-MAX HeapBy Sunarya D. Marwah
Copyright@Sunarya D. Marwah
Min-Max Heap adalah struktur binary tree, dimanasuatu node x berada di level min maka semua node dibawahnya, nilainya harus lebih besar dari nilainode x tersebut, dan bila node x berada di level max, maka seluruh node dibawahnya harus lebih kecil darinilai 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
DeleteDelete dari Min-Max Heap terdiri dari:
1. DeleteMin
2. DeleteMax
DeleteMin langsung mengambil elemen paling puncak yaitu level Min teratas , sedangkanDeleteMax harus memilih elemen terbesar di level Max teratas, baru melakukan DeleteMax.
Copyright@Sunarya D. Marwah
Min-MAX Heap
DeleteBaik DeleteMin maupun DeleteMax, penggantinode yang dihapus diambil dari node denganelemen terkecil dari anak-anak dan cucu-cucunya, kemudian elemen yang kosong diisidari elemen terakhir, kemudian lakukan reheap.
Contoh delete akan menggunakan konstruksiheap 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-anakdan 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 dibandingdengan Heap biasa, adalah DeleteMin dan DeleteMaxbisa dilakukan dalam satu struktur.
Copyright@Sunarya D. Marwah
Min-MAX Heap
top related