Heap and Tries

--- TUGAS BLOG ALGO-BINUS Mingguan ---

  Heap and Tries  

-------------------------------------
------------------------------------------------------

1. Heap

Heap adalah sebuah complete binary tree pada struktur data yang memenuhi properti heap. Properti heap yang dimaksud adalah min heap dan max heap.

Heap dapat diimplementasikan menggunakan linked-list, tapi akan lebih mudah jika menggunakan array.

2. Min-Heap

Pada min heap, setiap elemen node pada tree lebih kecil daripada children/anaknya. Hal ini berarti elemen/nilai terkecil pada tree tersebut harus terletak pada root dan nilai/elemen tertinggi pada tree terletak di salah satu leaf/daun.

Contoh min-heap tree:

3. Max-Heap

Pada max heap, setiap elemen node lebih besar daripada children/anaknya (kebalikan min-heap). Hal ini berarti elemen/nilai terkecil pada tree tersebut harus terletak pada salah satu leaf/daun dan nilai/elemen tertinggi pada tree terletak di root.

Contoh max-heap tree:

4. Heap Applications

Dalam pengaplikasi-an heap, dapat menggunakan Priority Queue dengan:
1. Selection Algorithms
2. Dijkstra's Algorithm
3. Prim Algorithm

Dapat juga menggunakan Heap Sort dengan: An O(n.lg(n)) algotihm.

5. Heap dengan Priority Queue

Implementasi heap efisien dengan priority queue struktur data.
1. find-min = mencari elemen/nilai terkecil dalam heap
2. insert = meng-insert/menambahkan elemen baru ke dalam heap
3. delete-min = menghapus elemen/nilai terkecil pada heap

delete-min disebut juga pop, sedangkan insert disebut juga push.

6. Heap dengan Array

Heap biasanya diemplementasikan melalui array. Elemen-elemen heap dalam array disimpan berdasarkan index 1 sampai N dengan berurutan dari atas kebawah dan dari kiri ke kanan node pada tree. *Root disimpan dalam index 1 (index 0 dibiarkan kosong/tidak digunakan)

Contoh heap dengan array:

Setiap node pada array ini berhubungan dengan parent, anak/child kiri, dan anak/child kanan nya masing-masing

Jika index dari suatu node adalah x, maka:

• Parent(x)          =   x / 2
• Left-child(x)     =   2 * x     -->(anak kiri(x))
• Right-child(x)   =   2 * x + 1     --> (anak kanan(x))

#rumus inilah yang menjadi alasan index pada heap array dimulai dari 1

7. Pengaplikasi-an Heap

Heap biasanya sering digunakan untuk:

• Sorting dengan heap
• Algoritma selection
• Algoritma Graph 

8. Tries

Tries atau prefix tree adalah sebuah tree yang tersusun/berurutan pada struktur data yang digunakan untuk menyimpan kumpulan array (biasanya berupa string). 

TRIES berasal dari kata RETRIEVAL, karena tries dapan menemukan sebuat kata dalam kamis dengan hanya dengan menggunakan kata depan dari kata tersebut.

9. Pengaplikasi-an Tries 

Contohnya adalah ketika sebuat web browser dapat otomatis menyelesaikan kata yang kita tulis (auto-complete) atau dengan menunjukkan pada pengguna banyaknya kemungkinan-kemungkinan dari teks yang akan ditulis. Contoh lainnya adalah spell-checker dalam mengecek kata yang ada dalam kamus apakah sudah sesuai apa belum.

10. Tree of Tries

Setiap vertex menyimpan sebuah kata atau kata depan.

Root dalam Tries menyimpan sebuah kata kosong ('").

Contoh Tries yang menyimpan/mengandung kata:

1. ALGO
2. API
3. BOM
4. BOX
5. BOSAN
6. BOR

10. Struktur Tries

Kita dapat menggunakan struktur ini dalam mengimplementasi tree:

struct trie {

  char chr;

  int  word;

  struct trie* edge[128];

} *root = 0;

root = (struct trie*)malloc(sizeof(struct trie));

root->chr  = ‘’;

root->word = 0;

note:    chr is the character stored in that node.

            word is 1 if there is a word ends at this node, 0 otherwise.

10. Insertion dalam Tries

Untuk menambahkan/memasukkan sebuah kata pada tries, kita dapat menggunakan kode:

main function

  char s[100];

  insert(root, s);

void insert(struct trie *curr, char *p) {

  if ( curr->edge[*p] == 0 )

       curr->edge[*p] = newnode(*p);

  if ( *p == 0 ) curr->word = 1;
     else insert(curr->edge[*p],p+1);

}

newnode() function

struct trie* newnode(char x) {

  struct trie* node =

      (struct trie*)malloc(sizeof(struct trie));

  node->chr  = x;

  node->word = 0;

  for (i = 0; i < 128; i++ )

       node->edge[i] = 0;

  return node;

}

11. Finding dalam Tries dengan Prefix

Untuk mencari sebuah kata lengkap jika kita memiliki sebuat kata awal dari kata tersebut, kita dapat menggunakan kode:

contoh mencari kata dengan awalan okay:

char s[100] = {“...”}; // global

int  i, n, okay;

struct trie *curr;

n    = strlen(s);

okay = 1;

curr = root;

for ( i = 0; i < n && okay == 1; i++ )

  if ( curr->edge[s[i]] == 0 ) okay = 0;

  else curr = curr->edge[s[i]];

if ( okay ) find(curr,n);

mengeprint semua kata lengkap yang memiliki awalan okay, dengan code :

void find(struct trie *curr, int x) {

  if ( curr->word == 1 ) {

      s[x] = 0;

      puts( s );

  }

  for ( i = 0; i < 128; i++ )

     if ( curr->edge[i] != 0 ) {

     s[x] = i;

     find(curr->edge[i],x+1);

     }

  }

-------------------------------------------------------------------------------------------------------------

Referensi:

• Power Point Heap and Tries (L)

-------------------------------------------------------------------------------------------------------------

Berikut adalah tugas mingguan membuat blog berisi rangkuman materi Heap and Tries yang telah saya pelajari.
Sekian,

---Terima kasih.---

   Nama: Felina Suryadi                  

   NIM: 2301914604                        

   Kelas Besar: CB01                        

-------------------------------------------------------------------------------------------------------------