Heap


Heap dibagi 2 yaitu max heap(elemen anak dari node lebih kecil) dan min heap (elemen anak dari node lebih besar) . Heap bisa diimplementasi dengan menggunakan array. Penggunaan heap bisa dalam selection algorithm, Djikstra’s algorithm dan Prim algorithm. Untuk sorting juga ada Heap Sort. Elemen dari heap disimpan secara sekuensial dalam array dari atas ke bawah, kiri ke kanan. Root selalu ditempatkan di index ke 1 untuk memudahkan perhitungan. Cara menentukan node relasi dari node x.
Parent= x/2, left-child = 2 * x, right-child = 2*x+1.
Insert dalam Min-Heap
1.      Taruh node pada index terahir dari array
2.      Upheap node tersebut untuk memperbaiki property heap
*Upheap : mencari elemen atas nya, jika elemen parentnya lebih besar maka elemen tersebut akan ditukar. Proses ini terjadi secara rekursif sampai kondisi tidak memenuhi(mencapai root atau elemen parent lebih kecil).
Delete dalam Min-Heap
1.      Delete elemen di root kemudian pindahkan elemen index terakhir ke posisi root, Downheap root untuk memperbaiki property heap
*Downheap : mencari kedua elemen anak, bandingkan ambil elemen anak dengan nilai yang lebih kecil, proses ini terus berlangsung sampai nilai child lebih besar atau elemen sudah mencapai leaf

Max-Heap memiliki property berkebalikan dengan min-heap tetapi semua operasinya sama saja

Min-Max Heap
Setiap level pada tree selang seling, antara max dan min. Hal ini memudahkan kita mencari nilai min dan max, nilai min terdapat pada root dan max terdapat pada salah satu child nya root
Insert pada Min-Max Heap
1.      Masukkan element baru pada index terakhir heap.
2.      Upheap elemen tersebut. Jika node berada pada level minimum, Terdapat 2 kondisi, jika parent dari node lebih kecil tukar nilai keduanya dan upheapmax dari parentnya jika tidak upheapmin dari node baru tersebut. Jika node berada pada level maksimum. Jika node parent lebih besar maka tukar nilai kedua node dan upheapmin dari parent jika tidak upheapmax dari node baru
*Upheapmin: bandingkan nilai node dengan parentnya jika nilai noded lebih kecil maka tukar kedua node dan lanjut upheapmin pada node grand-parent
*Upheapmax: bandingkan nilai node dengan parentnya jika nilai node lebih besar maka tukar kedua node dan lanjut upheapmax pada node grand-parent
Delete pada Min-Max Heap
1.      Delete elemen terkecil
a.      Tukar root dengan elemen terakhir dari heap
b.      Kurangi jumlah elemen dari heap
c.      Downheapmin dari root
2.      Delete elemen terbesar
a.      Tukar elemen left-child atau right-child  dari root(cari yang lebih  besar) dengan elemen terakhir dari heap
b.      Kurangi jumlah elemen dari heap
c.      Downheapmax dari node tersebut
*Downheapmin
- misal m adalah elemen terkecil pada anak atau cucu dari node yang sekarang.
- Jika m adalah cucu dari node yang sekarang:
-Jika m lebih kecil dari node yang sekarang maka tukar nilainya, Jika m lebih besar dari    parentnya tukar nilai keduanya. Lanjut downheaping dari m
                              - Jika m adalah anak dari node yang sekarang
                                 - Jika m lebih kecil dari node sekarang maka tukar nilai nya
                     * Downheapmax adalah kebalikan dari downheapmin
Tries
Tries(pohon prefix) adalah struktur data tree yang digunakan untuk menyimpan array asosiatif (biasanya string). Kegunaan tries untuk autocomplete, spellchecker pada kamus.
Sifat dari tries: rootnya berisi karakter kosong sehingga anaknya dapat berisi macam-macam alphabet hingga membentuk string

Link Referensi Penting: Heap Sort: https://www.geeksforgeeks.org/heap-sort/ , Binary Heap: https://www.geeksforgeeks.org/binary-heap/, Heap Visualization: https://www.cs.usfca.edu/~galles/visualization/Heap.html

Komentar

Posting Komentar

Postingan populer dari blog ini

Hash Table

1. Hash Table •  Hashing adalah teknik yang digunkan untuk menyimpan dan mengambil kunci dalam jangka waktu  yang cepat.  •  Dalam hashing, sebuah data misalnya string dapat diambil bagiannya(karakter) kemudian dijadikan key untuk disimpan pada table •  Hashing menggunakan indek untuk mengambil data pada penyimpanan untuk mempercepat pencaharian menggunakan hashed yang lebih pendek daripada nilai yang sebenarnya(lebih panjang). •  Hashing juga bisa disebut konsep mendistribusikan indeks kedalam sebuah  hash table menggunakan fungsi yang disebut  hash function . 2. Hash Function Ada banyak cara hashing string menjadi key. - Mid-Square - Division - Digit Extraction - Rotating Hash -Mid-Square     Key yang didapat dikudratkan kemudian diambil bagian tengah dari key     contohnya: key 3121 di kuadratkan menjadi 9740641 sehingga diambil bagian tengahnya 406    Penggunaan kuadrat agar address y...
Baca selengkapnya

Binary Search Tree (BST)

Struktur data binary search tree memberikan fitur searching dan sorting yang lebih cepat. insert dan delete yang lebih mudah juga.  Aturan penempatan node :  1. Untuk node yang lebih kecil dari node yang dibandingkan maka node tersebut ditempatkan dikiri 2. Untuk node yang lebih besar dari node yang dibandingkan maka node tersebut ditempatkan dikanan 3. Setiap node nilainya berbeda 4. Perbandingan mulai dari root, terus turun sampai dapat tempat kosong Operasi pada BST 1. search(x) 2. insert(x) 3. remove(x) 1. Search Misalnya nilai yang mau kita cari adalah x  - Mulai dari root  - Jika root mengandung x maka proses selesai  - Jika x < nilai root cari secara rekursif pada subtree kiri, Jika tidak maka cari  secara rekursif pada subtree kanan 2. Insert  Misalnya nilai yang ingin kita masukkan adalah x  - Proses mulai dari root  -  Jika x < nilai root cari secara rekursif pada subtree kiri, Jika tidak maka cari...
Baca selengkapnya