Heap adalah Complete binary tree yang
berbasis struktur data dan memenuhi aturan heap. Tree pada heap and deap tidak
memenuhi aturan BST yang harus terurut secara inorder, yang penting tree
tersebut mengikuti aturan heap. Heap biasanya diimplementasikan pada array dan
indexnya dimulai dari 1 bukan 0.
Heap dibagi menjadi 3 jenis
yaitu:
1. Min Heap: node paling
kecil adalah root dan semakin kebawah levelnya semakin besar
Cara insert:
Jika mi(elemen terkecil terletak di root): Masukkan data nya tidak seperti BST , melainkan dengan konsep array, sehingga kekanan terus, lalu kebawah, dst, atau bisa dikatakan bahwa elemen terakhir akan masuk ke index terakhir/menjadi anak paling kanan dan bawah. Data yang diinsert kemudian dibandingkan dengan parentnya, jika lbh kecil maka swap, lakukan terus menerus sampai root atau sampai data baru tersebut lebih besar dr parentnya.
Cara
delete:
Jika
min heap(elemen terkecil terletak di root): Maka yang dihapus merupakan
rootnya(elemen terkecil). Root yang dihapus tersebut kemudian digantikan oleh
data terakhir di nodenya, kemudian data tersebut di downheapmin(jika anak <
data tsb, maka tukar,dst sampai mentok dibawah atau node tsb<anaknya).
2. Max Heap: node
paling besar adalah root dan semakin kebawah levelnya semakin kecil
Cara insert:
Jika max heap(elemen terbesar terletak di root): Masukkan data nya tidak seperti BST , melainkan dengan konsep array, sehingga kekanan terus, lalu kebawah, dst, atau bisa dikatakan bahwa elemen terakhir akan masuk ke index terakhir/menjadi anak paling kanan dan bawah. Data yang diinsert kemudian dibandingkan dengan parentnya, jika lbh besar maka swap, lakukan terus menerus sampai root atau sampai data baru tersebut lebih kecil dr parentnya.
Cara delete:
Jika max heap(elemen terkecil terletak di root): Maka yang dihapus merupakan rootnya(elemen terbesar). Root yang dihapus tersebut kemudian digantikan oleh data terakhir di nodenya, kemudian data tersebut di downheapmax(jika anak > data tsb, maka tukar,dst), sampai mentok dibawah atau node tsb>anaknya).
3. Max-Min Heap: min-heap
dan max-heap levelnya saling bergantian pada tree
Cara insert:
·
Insert node baru (key) pada index
selanjutnya (setelah index terakhir)
1. jika
key terletak pada level min : bandingkan dengan parentnya
Jika parent < key maka swap dan
upheapmax dari parentnya (dibandingkan dengan grandparentnya dari posisi key
setelah swap)
Jika parent > key, upheapmin dari
posisi key (dibandingkan dengan grandparentnya dari posisi key).
2. jika
key terletak pada level max :
Jika parent > key maka swap dan
upheapmin dari parentnya (dibandingkan dengan grandparentnya dari posisi
keysetelah swap)
Jika parent < key, upheapmax dari
posisi key(dibandingkan dengan grandparentnya dari posisi key).
Cara delete:
terdapat 2 jenis delete,
yaitu delete min, dan delete max
- Delete Min, menghapus node terkecil, yaitu
root
- Delete Max, menghapus node terbesar, yaitu
salah satu dari anak root
konsep deletenya sama :
- node yang dihapus digantikan oleh node
index terakhir
- lakukan downheapmin
jika delete min, atau downheapmax jika delete max
Heap Sort merupakan salah satu dari 6 jenis metode sort atau sorting
(melakukkan pengurutan). Heap sort ini menggunakan teknik sorting dengan
menggunakan teknik heap. Teknik tersebut tersebut merupakan teknik pengelolaan
data yang menggunakan binary tree. Data yang dikelola maksudnya adalah
bagaimana data yang sudah terstruktur akan di organisir kembali jika kita
memasukkan data baru atau meng-insert data baru, atau pula menghapus data.
Teknik itulah yang diterapkan di metode heap sort. Inti dari pengurutan secara
heap adalah pengerjaannya yang dilakukkan dengan pengurutan ascending dan
descending, jadi ada dua kali pengurutan.
Tries
Tries adalah Binary Tree dimana isi dari tersebut adalah kumpulan dari kata-kata. Tree ini dibuat untuk mempermudah pencarian suatu kata-kata (biasanya digunakan pada saat pembuatan fitur search pada kamus).
No comments:
Post a Comment