HEAP
Heap adalah sebuah Tree yang mempunyai ketentuan sebagai berikut :
1. Tree harus complete binary Tree
- Semua level tree mempunyai simpul maksimum kecuali padda level terakhir.
- pada level terakhir, node tersusun dari kiri ke kanan tanpa ada yang di lewati.
2. Perbandingan nilai suatu node dengan nilai node childnya mempunyai ketentuan berdasarkan jenis Heap,diantaranya :
- Max Heap mempunyai ketentuan bahwa nilai suatu node lebih besar atau sama dengan(>=) dari nilai childnya.
- Min Heap mempunyai ketentuan bahwa nilai suatu node lebih kecil atau sama dengan (<=) dari nilai childnya.
Ada 2 Jenis Heap :
1. Min Heap : Node paling kecil adalah root dan semakin kebawah levelnya semakin besar.
2. Max Heap : node paling besar adalah root dan semakin kebawah levelnya semakin kecil.
3. Min-Max Heap : min-heap dan max-heap levelnya saling bergantian pada tree.
 |
| Contoh Max Heap dan Min Heap. |
Heap biasanya diimplementasikan pada array dan indexnya dimulai dari 1, bukan 0.
Cara Mengetahui Lokasi Index parent dan child :
1. Parent(x) = x/2 ,dengan x = index Child
2. Left-Child(x)= 2*x ,dengan x = index parent
3. Right-Child(x)=2*x+1 ,dengan x = index parent.
Operasi pada Heap ada 2 Macam yaitu Insertion dan Deletion.
Insertion
pada heap , saat node baru di masukkan ia akan memenuhi anaknya terlebih dahulu (kiri ke kanan),
Dalam Proses Insert , ada namanya UpHeap / HeapifyUp (Yang artinya kalau node tersebut lebih kecil dia akan naik (Min Heap ) , atau kalau node tersebut besar node tersebut akan naik (Max Heap)).
Insertion MinHeap
1. Insert node baru pada index selanjutnya (setelah index terakhir).
2. Lakukan UpHeap,yaitu membandingkan key dengan parentnya . Jika node parent > key, maka di swap. Jika tidak maka biarkan saja.
3. Lakukan point ke-2 berulang kali jika setelah diswap masih parent>key. Namun stop jika key sudah berada pada posisi root.
Contoh :
Insert 5
Insertion MaxHeap
1. Insert Node baru(Key) pada index selanjutnya (setelah index terakhir)
2. Lakukan UpHeap, yaitu membandingkan key dengan parentnya . Jika node parent < key, maka di swap. Jika tidak maka biarkan saja.
3. Lakukan point ke-2 berulang kali jika setelah diswap masih parent<key. Namun stop jika key sudah berada pada posisi root.
Contoh:
Insert 15
DELETION
Kebalikan dari proses insert di dalam deletion ada namanya DownHeap / HeapifyDown
Min Heap Deletion
Aturan :
- Operasi delete hanya terjadi pada rootnya saja.
- gantikan elemen yang di delete dengan node yang berada pada index terakhir.
- lakukan downHeap, yaitu membandingan dengan salah satu childnya yang terkecil. Jika node tersebut > child terkecil , maka swap.
- Lakukan point ke-3 berkali kali jika setelah diswap node tersebut masih memiliki anak. Namun Stop jika node sudah dalam posisi leaf atau node tersebut < child terkecilnya.
Contoh:
Delete 7
Max Heeap Deletion
Aturan :
- Operasi delete hanya terjadi pada rootnya saja.
- gantikan elemen yang di delete dengan node yang berada pada index terakhir.
- lakukan downHeap, yaitu membandingan dengan salah satu childnya yang terbesar. Jika node tersebut < child terbesar , maka swap.
- Lakukan point ke-3 berkali kali jika setelah diswap node tersebut masih memiliki anak. Namun Stop jika node sudah dalam posisi leaf atau node tersebut > child terbesarnya.
Min-Max Heap
Min-Max Heap adalah penggabungan dari min-Heap dan Max-Heap. Dimana pada tree ini kita dapat mendapatkan 1 angka terkecil dan 2 angka terbesar. Namun sayangnya , angka terbesar tersebut salah satunya memang terbesar tetapi satunya lagi belum pasti nilai terbesar keduanya.
Contoh:
Level pertama pada Min-Max heap addalah min level dibawhanya max level. Nilai terkecil pada tree terletak pada rootnya, sedangkan 2 nilai terbesarnya adalah anak dari rootnya.
Insert Min-Max Heap
1. Insert node baru(key) pada index selanjutnya (setelah index terakhir)
2. Jika key terletak pada level min:bandingan dengan parentnya
- Jika parent < key maka swap dan UpHeap Max dari parentnya(Bandingkan dengan grand parentnya dari posisi key setelah di swap)
- Jika parent > key, Upheap Min dari posisi key(Bandingkan dengan GrandParentnya dari posisi key).
3. Jika key terletak pada level max :
- Jika parent > key maka swap dan UpHeap Min dari parentnya (bandingkan dengan GrandParentnya dari posisi key setelah di swap).
- Jika parent < key, UpHeap Max dari posisi key(Bandingkan dengan grandParentnya dari posisi key).
Deleteion Min-Max Heap
ada 2 jenis delete, yaitu delete min , dan delete max
1. Delete min , menghapus node terkecil, yaitu root
2. Delete Max,Menghapus node terbesar, yaitu salah satu dari anak root
Heap Sort
Min Sort -> Ascending
Max Sort -> Descending
Jadi jika kita mempunyai angka
10,15,12,18,20,17,28,21,35,22
Kita kalau mau mengurutkannya dengan cara di tampung.
Caranya :
1 . Menampung Root an hapus root tersebut sementara
2. Lakukan swap seperti biasa .
3. lakukan cara yang di atas sampai semua angka tertampung
4. Kemudian Insert seperti biasa.
TRIES
Tries atau prefix Tree adalah suatu pohon struktur data yang terurut yang menyimpan data array, biasanya String. Kata tries diambil dari kata RETRIEVAL, karena tries dapat menemukan katatunggal dalam kamus hanya dengan awalan katanya saja.
Tries sudah diterapkan ke banyak hal dalam kehidupan sehari-hari,contohnya pada web browser. Suatu web browser dapat mengira atau mensugestikan kata-kata yang mungkin kita maksud saat kita mengetik huruf pertamanya saja (autocomplete).
Contoh :
Kemudian selain itu juga pada spell checker,spell checker dapat mengetahui spelling kata yang tepat saat kita melakukan kesalahan dalam pengetikan.
Tries adalah suatu tree dimana setiap vertex/Pathnya menggambarkan suatu kata,rootnya kosong.
Daftar Pustaka :
Tidak ada komentar:
Posting Komentar