Heaps & Tries Summary

Pada minggu ini kami belajar heaps & tries, berikut adalah rangkuman saya:

Heap:

Heap adalah complete binary tree yang memenuhi properti heap.

Properti heap terdapat 2 yaitu:

1. Min heap:

           Setiap elemen pada node lebih kecil dari pada childnya.

2. Max heap:

           Setiap elemen pada node lebih besar dari pada childnya

Min Heap:

Pada min heap setiap element pada node lebih kecil dari pada childnya dan elemen terkecil terdapat di root.

Berikut adalah contoh gambar Min Heap:

Heap biasanya diimplementasikan pada array dan dimulai dari index 1 agar lebih mudah untuk relasi node parent, left dan right childnya.

Untuk mencari tahu index dari node parent, left dan right child sebuah node adalah

Misalkan index node nya adalah x maka:

Index Parent(x)                = x / 2

Index Left-child(x) = 2 * x

Index Right-child(x) = 2 * x + 1

Insertion pada Min Heap:

Node baru diinsertkan pada akhir heap atau setelah index terakhir pada array.

Setelah itu perbaiki heapnya agar memenuhi property heap dengan cara upheap.

Berikut adalah code untuk Insert Min-Heap:
void insertHeap(int x) {
    nelement++;  //Tambahkan jumlah elemen di array
    arrHeap[nelement] = x;  //elemen baru dimasukkan pada akhir array
    upHeap(nelement);  //Lalu upheap element tersebut
}

Upheap pada Min Heap:
Bandingkan nilai pada node sekarang dengan parentnya. Jika nilai pada node sekarang lebih kecil dari pada parent maka ditukar. Lalu dengan parentnya lagi dan seterusnya hingga nilai pada parent node lebih kecil dari pada node sekarang.

Berikut adalah gambar contoh dari upheap pada min heap:

Berikut adalah code untuk Upheap pada Min-Heap:
void upHeap(int index) {
    if (index == 1) return;  //Jika elemennya di root berarti upheap berhenti
   
    int parentIndex = index / 2;
   
    if (arrHeap[index] < arrHeap[parentIndex]) {
        swap(&arrHeap[index], &arrHeap[parentIndex]);  //Jika parent lebih besar dari pada element 
                                                                                           maka ditukar
        upHeap(parentIndex);  //Lalu upheap lagi
    }
}

Deletion pada Min Heap:

Deletion pada Min heap hanya menghapus rootnya saja atau delete elemen terkecil. Setelah dihapus maka digantikan dengan node terakhir pada heap. Setelah itu perbaiki heapnya agar memenuhi property heap dengan cara downheap.
Berikut adalah code untuk Deletion pada Min-Heap:
void deleteMin() {
//Pada code ini yang dihapus itu root atau elemen min
    if (nelement == 0) {
        printf("Heap is empty!\n");
      }
    if (nelement == 1) {
        nelement--;
      }

    swap(&arrHeap[1], &arrHeap[nelement]);  //Pertama tukar nilai pada root/minnya dengan elemen pada array terakhir
    nelement--;  //Lalu didelete elemen terakhir pada array
   
    downHeap(1);  Lalu downheap elemen pada root
}

Downheap pada Min Heap

Bandingkan  nilai pada node sekarang dengan left dan right childnya. Jika node sekarang lebih kecil dari pada left dan right child maka tukarkan dengan child yang terkecil. Lalu bandingkan dan tukarkan lagi dengan child berikutnya hingga node sekarang lebih kecil dari pada kedua childnya atau sudah sampai leaf.

Berikut adalah gambar contoh dari deletion dan downheap pada min heap:

Berikut adalah code untuk DownHeap pada Min-Heap:
void downHeap(int index) {
    int toIndex = index;
    if (2*index <= nelement && arrHeap[index] > arrHeap[2*index]) {
        toIndex = 2*index;
    }
    if (2*index+1 <= nelement && arrHeap[toIndex] > arrHeap[2*index+1]) {
        toIndex = 2*index+1;
    }
    if (index == toIndex) return;
    swap(&arrHeap[index], &arrHeap[toIndex]);
    downHeap(toIndex);
}

Max Heap:

Pada max heap setiap element pada node lebih besar dari pada childnya dan elemen terbesar terdapat di root.

Insertion dan deletion pada Max Heap kurang lebih sama seperti pada Min Heap bedanya adalah jika upheap pada Min heap node sekarang ditukar dengan parentnya jika node sekarang lebih kecil dari pada parent. Tetapi pada Max heap node sekarang ditukar dengan parentnya jika node sekarang lebih besar dari pada parent.

Kemudian down heap pada Min heap  node sekarang ditukar dengan childnya yang lebih kecil sedangkan pada Max Heap node sekarang ditukar dengan childnya yang lebih besar.

Min-Max Heap:

Pada Min-max heap kondisi heapnya berganti-ganti antara min dan max di setiap level. Pada level yang ganjil maka  node nya lebih kecil dari pada childnya sedangkan pada node yang genap maka nodenya lebih besar dari pada childnya.

Berikut adalah contoh gambar min-max heap:

Insertion pada min max heap :

Insertion node baru pada min-max heap dimasukkan pada akhir heap atau setelah index terakhir di array. Setelah itu di upheap untuk memenuhi properti heapnya. Tetapi insertion pada min max heap berbeda yaitu:

Jika node baru terdapat pada min-level maka :

Jika parent node baru lebih kecil dari pada node baru tukar value mereka lalu upheapmax dari parentnya. Jika parent node baru tidak lebih kecil dari pada node baru maka upheapmin dari node baru.

Jika node baru terdapat pada max level maka:
jika parent node baru lebih besar dari pada node baru maka tukarkan nilai mereka dan upheapmin dari parentnya. Jika parent node baru tidak lebih besar dari pada node baru maka upheapmax dari node baru.

Upheapmax dan Upheapmin

Upheapmin: bandingkan nilai node sekarang dengan nilai grand parentnya. Jika nilai node sekarang lebih kecil daripada nilai grand parentnya maka tukarkan nilai mereka dan lanjutkan upheapmin pada grand-parent node.

Berikut adalah contoh gambar upheapmin:

Upheapmax: bandingkan nilai node sekarang dengan nilai grand parentnya. Jika nilai node sekarang lebih besar daripada nilai grand parentnya maka tukarkan nilai mereka dan lanjutkan upheapmax pada grand-parent node.

Berikut adalah contoh gambar upheapmax:

Deletion pada Min-Max Heap

Deletion elemen terkecil:

-Ganti root dengan elemen terakhir di heap

-Hapus elemen terakhir di heap

-Downheapmin dari root

Deletion elemen terbesar:

Ganti left atau right child dari root dengan elemen terakhir di heap.

Hapus elemen terakhir di heap

Downheapmax dari node yang diganti tadi.

Downheapmin:
Jika m adalah elemen terkecil dari child dan grandchild node sekarang maka:

-          Jika m adalah grandchild dari node sekarang maka:

o   Tukar nilai mereka

o   Jika m lebih besar dari pada parentnya maka tukar nilai mereka

o   Lanjutkan downheapmin dari m

-          Jika madalah child dari node sekarang maka:

o   Jika m lebih kecil dari node sekarang maka tukar nilai mereka.

Downheapmax:

Jika m adalah elemen terbesar dari child dan grandchild node sekarang maka:

-          Jika m adalah grandchild dari node sekarang maka:

o   Tukar nilai mereka

o   Jika m lebih kecil dari pada parentnya maka tukar nilai mereka

o   Lanjutkan downheapmax dari m

-          Jika m adalah child dari node sekarang maka:

o   Jika m lebih besar dari node sekarang maka tukar nilai mereka. 

Berikut adalah contoh gambar dari Downheapmax:

Tries

Tries adalah struktur data tree terurut yang digunakan untuk menyimpan array asosiatif (biasanya string)

Tries ini biasanya digunakan untuk spell checker.

Tries adalah sebuah tree dimana setiap vertex melambangkan satu kata atau prefix.

Root dari Tries adalah karakter kosong atau (‘’)

Berikut adalah contoh gambar dari Tries: