Heap & Priority Queue Struktur Data
Muhammad Riza Hilmi, ST.
[email protected]
Priority Queue ●
●
Priority Queues (pengembangan lebih lanjut dari konsep Queue) yaitu sebuah queue yang setiap komponen terdiri atas key dan value. Priority queue mirip antrian, yaitu penghapusan / pengurangan anggota selalu dilakukan pada anggota antrian yang terdepan dan penambahan anggota selalu dilakukan dari belakang antrian berdasarkan prioritas anggota tersebut, akan tetapi pada priority queue diliat dari prioritasnya (anggota yang memiliki prioritas lebih besar selalu berada di depan anggota yang memiliki prioritas lebih rendah).
Priority Queue ●
Contohnya ketika kita mengantri di rumah sakit, pastilah orang yang sakitnya lebih parah akan didahulukan dalam antrian. Dalam kasus ini yang menjadi prioritas dari sebuah antrian di rumah sakit adalah tingkat keparahan pasien.
Validasi Priority Queue : (prioritas yang lebih besar dilihat dari nilai yang terkecil) ●
●
●
Jika nilai prioritas data yang akan dipush lebih kecil dari prioritas data pada head maka kita akan push data ke depan head (push depan). Jika nilai prioritas data yang akan dipush lebih besar atau sama dengan data pada tail maka kita akan push data ke belakang tail (push belakang). Selain itu maka data akan di push ke tengah antrian dengan syarat data dengan nilai prioritas yang sama akan ditaruh ke antrian paling belakang dari antrian dengan nilai prioritas yang sama.
Implementasi Priority Queue ●
●
Salah satu contoh Implementasi Priority Queue adalah Heap Tree. Suatu heap tree adalah Complete Binary Tree (CBT) di mana nilai key pada node-nodenya sedemikian rupa sehingga nilai key pada node-node anaknya tidak ada yang lebih besar dari nilai key pada node orang tuanya.
Heap Tree ●
●
Heap merupakan sebuah Tree yang memenuhi syarat Binary Tree secara lengkap, terdiri atas internal node dan external node dan setiap internal node menyimpan sebuah nilai. Nilai-nilai pada setiap node-nya memenuhi syarat Heap Minimum atau Heap Maksimum. Heap Maksimum jika nilai root lebih besar dari nilai left child dan right child, sedangkan Heap Minimum jika nilai root lebih kecil dari nilai left child dan right child.
Gambar Contoh Heap Minimum
Gambar Contoh Priority Queue pada Heap
Representasi Heap ✔
Root at location 0
✔
Left child of i is at location 2i + 1
✔
Right child of i is at location 2i + 2 = 2(i + 1)
Ilustrasi Insert Node #1 Jika ingin memasukkan atau menyisipkan node baru, letakkan pada sebuah memori kosong bagian akhir.
Setelah itu, bandingkan node baru dengan root (parent) nodenya.
Ilustrasi Insert Node #2 Jika node baru lebih kecil daripada root (parent) nodenya, maka tukar nilainya. Selanjutnya bandingankan dengan root (parent) nodenya lagi, jika node baru lebih besar daripada root (parent) node, maka nilainya tidak ditukar.
Ilustrasi Remove Node #1 Penghapusan node, dilakukan pada root (parent) node. Kosongkan root (parent) nodenya.
Selanjutnya, isikan dengan isi dari node yang posisinya paling akhir.
Ilustrasi Remove Node #2 Bandingkan root (parent) nodenya dengan child node yang paling kiri terlebih dahulu, jika ada diantara child node nilainya lebih kecil dari root node, maka tukar nilainya.
Lakukanlah perbandingan dengan semua node sehingga datanya terurut dengan baik sesuai dengan syarat minimum head atau maksimum head.
