Heaps dan Tries

-

Heaps dan Tries

Heap

Heap adalah struktur data berbasis pohon biner lengkap yang memenuhi properti heap. Heap properti terbagi menjadi 3 bagian yaitu Min-Heap, Max-Heap, dan Min-Max Heap. Mari kita bahas satu persatu seperti dibawah ini:

Aplikasi Heap
  • Priority Queue
  • Selection Algorithms (menemukan elemen min / maks, median, elemen kth-terbesar, dll).
  • Dijkstra’s Algorithm (menemukan jalur terpendek dalam grafik)
  • Prim Algorithm (menemukan minimum spanning tree)
  • Heap Sort
  • An O(n.lg(n)) algorithm.
Implementasi Array 
  • Heap biasanya diimplementasikan didalam array.
  • Elemen-elemen nya tersimpan secara berurutan adri index 1 sampai N dari atas sampai bawah dan dari kiri ke kanan dari node of the tree .
  • Root tersimpan dari index 1 (kita biarkan index 0 kosong/tidak terpakai, demi kenyamanan)
Setiap hubungan node dengan orang tuanya, anak kiri dan anak kanan dalam implementasi array dapat dihitung dengan mudah.

Biarkan indeks simpul saat ini menjadi x.
Induk (x) = x / 2
Anak kiri (x) = 2 * x
Anak kanan (x) = 2 * x + 1

Inilah mengapa kami menggunakan indeks 1 sebagai root, jika tidak
hubungan tidak akan muncul sesederhana ini.

1. Min-Heap





  • Setiap elemen node lebih kecil dari elemen child nya.





  • Ini menyiratkan bahwa elemen terkecil terletak di akar pohon (root of the tree).





  • Elemen terbesar terletak di suatu tempat di salah satu  node's leaf.





  • Heap dapat diimplementasikan menggunakan linked-list, tetapi jauh lebih mudah untuk              mengimplementasikan heap menggunakan array.


    • Min-Heap

    Insertion pada Min-Heap
    • Jika ingin memasukkan elemen baru ke dalam heap, tetapi kita harus mempertahankan properti heapnya.
    • Masukkan elemen baru di akhir heap (setelah indeks elemen terakhir).
    • Upheap elemen baru (memperbaiki properti heap nya).
    Upheap pada Min-Heap
    • Bandingkan nilai node saat ini (mulai dengan node yang dimasukkan) dengan nilai parent nya. Jika nilai node saat ini lebih kecil dari nilai parent nya maka kita menukar nilainya dan teruskan upheap node parent nya.
    • Berhenti jika nilai parent nya lebih kecil dari nilai node saat ini atau node saat ini adalah root (tidak memiliki parent).
    Insert (20)

    Insert (5)
    Continue

    Deletion pada Min-Heap
    • Di sini kita hanya membahas penghapusan elemen terkecil yang terletak di root
    • Ganti root dengan elemen terakhir dari heap.
    • Kurangi jumlah elemen dalam tumpukan.
    • Downheap root (memperbaiki properti heapnya).
    Downheap pada Min-Heap
    • Bandingkan nilai node saat ini (mulai dengan root) dengan nilai anak kiri dan kanannya. Tukar node saat ini dengan child terkecil dan lanjutkan downheap pada node (child) itu.
    • Berhenti jika nilai node saat ini lebih kecil dari nilai child nya atau node saat ini adalah lef (tidak memiliki child).
    Berikut saya sertakan code insertion, deletion untuk Min-Heap:

    #include<stdio.h>
    #include<string.h>
    #include<windows.h>

    int minHeap[100000] = {};

    void cls()
    {
    for(int i = 0; i < 30; i++) puts("");
    }

    void swap(int *a, int *b)
    {
    int t = *a;
    *a = *b;
    *b = t;
    }

    void checkHeapAdd(int idx)
    {
    if(idx == 1)
    return;
    else
    {
    if(minHeap[idx] < minHeap[idx/2])
    {
    swap(&minHeap[idx],&minHeap[idx/2]);
    checkHeapAdd(idx/2);
    }
    }
    }

    void checkHeapRemove(int idx, int root)
    {
    if(idx > 100000 || (minHeap[root*2] == 0 && minHeap[root*2+1] == 0))
    return;
    else
    {
    if(minHeap[root*2] != 0 && minHeap[root] > minHeap[root*2])
    {
    swap(&minHeap[root],&minHeap[root*2]);
    checkHeapRemove(idx,root*2);
    }
    else if(minHeap[root*2 + 1] != 0 && minHeap[root] > minHeap[root*2 + 1])
    {
    swap(&minHeap[root],&minHeap[root*2 + 1]);
    checkHeapRemove(idx,root*2+1);
    }
    }
    }

    int insertNode(int idx)
    {
    char value[11];
    int tValue;
    do
    {
    printf("Insert value [value > 0] : ");
    scanf("%[^\n]",value);
    while(getchar() != '\n');
    tValue = atoi(value);
    }
    while(tValue < 1);
    minHeap[idx] = tValue;
    checkHeapAdd(idx);
    printf("%d has been added!\n",tValue);
    while(getchar() != '\n');
    return (++idx);
    }

    int deleteNode(int idx)
    {
    if(minHeap[1] == 0)
    {
    printf("There is no data yet . . .\n");
    printf("Press Enter to continue . . .");
    while(getchar() != '\n');
    return 1;
    }
    printf("Root = %d has been deleted!\n",minHeap[1]);
    idx--;
    minHeap[1] = minHeap[idx];
    minHeap[idx] = 0;
    checkHeapRemove(idx,1);
    printf("Press Enter to continue . . .");
    while(getchar() != '\n');
    return (idx);
    }

    void findMin()
    {
    if(minHeap[1] == 0)
    {
    printf("There is no data yet . . .\n");
    printf("Press Enter to continue . . .");
    while(getchar() != '\n');
    return;
    }
    printf("Min Value = %d\n",minHeap[1]);
    printf("Press Enter to continue . . .");
    while(getchar() != '\n');
    }

    void menu()
    {
    puts("Min-Heap Menu :");
    puts("1. Find Min");
    puts("2. Insert");
    puts("3. Delete");
    puts("4. Exit");
    printf("Choose : ");
    }

    int init() {
    minHeap[1] = 3;
    minHeap[2] = 10;
    minHeap[3] = 5;
    return 4;
    }

    int main()
    {
    int choose = 0;
    int idx = 1;
    idx = init();
    do
    {
    cls();
    menu();
    scanf("%d",&choose); while(getchar() != '\n');
    switch(choose)
    {
    case 1:
    cls();
    findMin();
    break;
    case 2:
    cls();
    idx = insertNode(idx);
    break;
    case 3:
    cls();
    idx = deleteNode(idx);
    break;
    }
    }
    while(choose != 4);
    return 0;
    }

    2. Max-Heap
    • Setiap elemen node lebih besar dari elemen anak-anaknya.
    • Ini menyiratkan bahwa elemen terbesar terletak di root (akar pohon).
    • Max-heap memiliki prinsip yang sama dengan min-heap dan dapat digunakan untuk membuat priority queue yang perlu menemukan elemen terbesar alih-alih yang terkecil.
    3. Min-Max Heap
    • Kondisi heap bergantian antara level minimum dan maksimum dari level ke level.
      • Setiap elemen pada level genap / ganjil lebih kecil dari semua anak-anaknya (level min).
      • Setiap elemen pada level ganjil / genap lebih besar dari semua anak-anaknya (level maksimal).
    • Tujuan dari Min-Max Heap adalah untuk memungkinkan kita menemukan elemen tumpukan terkecil dan terbesar sekaligus.
    Dalam Min-Max Heap,
    • Elemen terkecil terletak di root.
    • Elemen terbesar terletak di salah satu anak root (baik anak kiri / kanan).
    Catatan: elemen terbesar mungkin terletak di root jika hanya ada satu elemen di heap.

    findmin () {return data [1]; }
    findmax () {return max (data [2], data [3]); }



    Insertion pada Min-Max Heap
    • Masukkan elemen baru di akhir heap (setelah indeks elemen terakhir).
    • Angkat elemen baru (memperbaiki properti heap nya).
    Upheap dalam min-max heap sedikit berbeda dengan min-heap atau max-heap.

    Upheap Min-Max

    • Jika node baru berada pada level min
      • Jika induk node baru lebih kecil dari itu, maka tukarkan nilainya dan upheapmax dari induknya.
      • Lain upheapmin dari node baru
    • Jika simpul baru berada pada level maksimal
      • Jika induk simpul baru lebih besar dari itu, maka tukar nilainya dan upheapmin dari induknya.
      • Lain upheapmax dari node baru
    Upheap min/max pada Min-max Heap

    Upheapmin
    • Bandingkan nilai node saat ini dengan nilai grand-parent-nya. Jika
    • nilai node saat ini lebih kecil dari nilai induknya daripada swap
    • nilai-nilai mereka dan teruskan sampai simpul grand-parent.
    Upheapmax
    • Bandingkan nilai node saat ini dengan nilai grand-parent-nya. Jika
    • nilai node saat ini lebih besar dari nilai induknya daripada swap
    • nilai-nilai mereka dan teruskanmaxmax node grand-parent.
        Min Max Heap Insert 50

    Upheapmin: 50 lebih besar dari induknya, jadi lakukan upheapmax
    Upheapmax: 50 lebih besar dari grand-parent-nya, jadi tukarkan nilainya

    Deletion in Min-Max Heap

    • Penghapusan elemen terkecil
      • Ganti root dengan elemen terakhir di heap.
      • Kurangi jumlah elemen dalam tumpukan.
      • Downheapmin dari root.
    • Penghapusan elemen terbesar
      • Ganti anak kiri atau anak kanan root (tergantung mana yang lebih besar) dengan elemen terakhir di heap.
      • Kurangi jumlah elemen dalam tumpukan.
      • Downheapmax dari node.
    Downheap Min/Max in Min-Max Heap

    Downheapmin

    • Misalkan m adalah elemen terkecil dalam anak dan cucu simpul saat ini (jika ada).
    • Jika m adalah cucu dari simpul saat ini
      • Jika m lebih kecil dari node saat itu
        • Tukar nilai mereka.
        • Jika m lebih besar dari induknya, maka tukarkan nilainya
        • Lanjutkan downheapmin dari m
    • Jika m adalah anak-anak dari simpul saat ini
      • Jika m lebih kecil dari node saat itu
        • Tukar nilai mereka
    • Downheapmax adalah sama kecuali bahwa operator relasional dibalik.
    Aplikasi dari Heap:

    Heap lebih digunakan untuk aplikasi yang meliputi:
    • Heap sort
      • itu adalah salah satu metode penyortiran terbaik yang tidak memiliki skenario terburuk kuadrat
    • Algoritma seleksi
      • algoritma ini digunakan untuk menemukan nilai minimum dan maksimum dalam waktu linear atau sub-linear
    • Algoritma grafik
      • Karena itu, tumpukan digunakan untuk mengimplementasikan algoritma spanning tree minimal Prim dan masalah jalur terpendek Dijkstra


    Tries

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

    Istilah TRIE berasal dari kata RETRIEVAL, karena mencoba dapat menemukan satu kata dalam kamus dengan hanya awalan kata.


    • Tries adalah pohon di mana setiap simpul mewakili satu kata atau awalan.
    • Root mewakili karakter kosong (‘’).
    • Sebuah vertex yang merupakan k edge jarak dari root memiliki awalan terkait panjang k.
    • Biarkan a dan b menjadi dua simpul dari percobaan dan menganggap a adalah induk langsung dari b, maka b harus memiliki awalan terkait a.

    Aplikasi dari Trie

    • Apakah Anda tahu bagaimana browser web dapat secara otomatis melengkapi teks Anda atau menunjukkan kepada Anda banyak kemungkinan teks yang bisa Anda tulis?
    • Apakah Anda tahu bagaimana pemeriksa ejaan dapat memeriksa bahwa setiap kata yang Anda ketikkan ada dalam kamus?
    • Apakah Anda tahu bagaimana pemeriksa ejaan dapat menyarankan koreksi kata yang salah ketik?

    Contoh dari Tries yang berisi kata-kata:


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









    Struktur Tries:

    Kita dapat menggunakan struktur ini untuk mengimplementasikan Tries:

    struct trie {
    char chr;
    kata int;
    struct trie * edge [128];
    } * root = 0;

    root = (struct trie *) malloc (sizeof (struct trie));
    root-> chr = ‘’;
    root-> word = 0;

    note:

    • chr adalah karakter yang disimpan dalam simpul itu.
    • kata adalah 1 jika ada kata berakhir di simpul ini, 0 sebaliknya.

    Insertion pada Tries


    Untuk memasukkan kata ke dalam Tries, kita dapat menggunakan kode ini:

    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;
    }

    Menemukan Tries menggunakan Prefix

    Misalkan kita ingin menemukan semua string dalam percobaan yang memiliki awalan tertentu.

    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);

    dan fungsi find (ini akan mencetak semua string yang memiliki awalan)

    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);
    }
    }


     Berikut saya sertakan code untuk Tries:

    // Source: https://www.geeksforgeeks.org/trie-insert-and-search/
    // C implementation of search and insert operations
    // on Trie

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <stdbool.h>

    #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])

    // Alphabet size (# of symbols)
    #define ALPHABET_SIZE (26)

    // Converts key current character into index
    // use only 'a' through 'z' and lower case
    #define CHAR_TO_INDEX(c) ((int)c - (int)'a')

    // trie node
    struct TrieNode
    {
    struct TrieNode *children[ALPHABET_SIZE];

    // isEndOfWord is true if the node represents
    // end of a word
    bool isEndOfWord;
    };

    // Returns new trie node (initialized to NULLs)
    struct TrieNode *getNode(void)
    {
    struct TrieNode *pNode = NULL;

    pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode));

    if (pNode)
    {
    int i;

    pNode->isEndOfWord = false;

    for (i = 0; i < ALPHABET_SIZE; i++)
    pNode->children[i] = NULL;
    }

    return pNode;
    }

    // If not present, inserts key into trie
    // If the key is prefix of trie node, just marks leaf node
    void insert(struct TrieNode *root, const char *key)
    {
    int level;
    int length = strlen(key);
    int index;

    struct TrieNode *pCrawl = root;

    for (level = 0; level < length; level++)
    {
    index = CHAR_TO_INDEX(key[level]);
    if (!pCrawl->children[index])
    pCrawl->children[index] = getNode();

    pCrawl = pCrawl->children[index];
    }

    // mark last node as leaf
    pCrawl->isEndOfWord = true;
    }

    // Returns true if key presents in trie, else false
    bool search(struct TrieNode *root, const char *key)
    {
    int level;
    int length = strlen(key);
    int index;
    struct TrieNode *pCrawl = root;

    for (level = 0; level < length; level++)
    {
    index = CHAR_TO_INDEX(key[level]);

    if (!pCrawl->children[index])
    return false;

    pCrawl = pCrawl->children[index];
    }

    return (pCrawl != NULL && pCrawl->isEndOfWord);
    }

    // Driver
    int main()
    {
    // Input keys (use only 'a' through 'z' and lower case)
    char keys[][8] = {"the", "a", "there", "answer", "any",
    "by", "bye", "their"};

    char output[][32] = {"Not present in trie", "Present in trie"};


    struct TrieNode *root = getNode();

    // Construct trie
    int i;
    for (i = 0; i < ARRAY_SIZE(keys); i++)
    insert(root, keys[i]);

    // Search for different keys
    printf("%s --- %s\n", "the", output[search(root, "the")] );
    printf("%s --- %s\n", "these", output[search(root, "these")] );
    printf("%s --- %s\n", "their", output[search(root, "their")] );
    printf("%s --- %s\n", "thaw", output[search(root, "thaw")] );

    return 0;
    } 



    References: Binus University resources Data Structures (Heaps&Tries Session 11).
                        Additional material from Lab Assistant.
                         https://www.geeksforgeeks.org/trie-insert-and-search/C implementation of search and                          insert operations on Trie .












    Komentar

    Posting Komentar

    Postingan populer dari blog ini

    AVL Tree

    -
    Gambar
    AVL TREE ---English Version--- Before we start to AVL Tree let's review Binary Search Tree (BST). Binary Search Tree This picture is the example of a skewed Binary Search Tree (BST). The left BST is inserted by 2, 5, 7, 8, and 13 respectively.  The right BST is inserted by 9, 1, 6, 3, and 4 respectively. AVL Tree AVL Tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one of all nodes. Height of a node: The height of an empty subtree is 0. The height of a leaf is 1. The height of an internal node is the maximum height of its children plus 1. Balance factor: The difference height of its LEFT subtree and its RIGHT subtree. The balance factor of all nodes in the AVL Tree should be at most 1. AVL Tree has two operations such as: 1. Insertion 2. Deletion AVL Tree Operation (Insertion) Look at the picture above, isn't it co...
    Baca selengkapnya

    Binary Search Tree

    -
    Gambar
    Binary Tree Binary Tree adalah struktur data yang mirip dengan Linked List. Bila Linked List dianalogikan sebagai rantai yang linier maka Binary Tree dianalogikan sebagai pohon. Binary Tree dikelompokkan menjadi tree yang tidak berurut (unordered Binary Tree) dan tree yang terurut (ordered Binary Tree). Binary Tree dapat digambarkan berdasarkan kondisinya, yaitu:  Binary Search Tree (BST) merupakan tree yang terurut (ordered Binary Tree) yang memiliki kelebihan bila dibanding dengan struktur data lain. Diantaranya adalah proses pengurutan (sorting) dan pencarian (searching) dapat dilakukan bila data sudah tersusun dalam struktur data BST. Pengurutan dapat dilakukan bila BST ditelusuri (traversed) menggunakan metode in-order. Detail dari proses penelusuran ini akan dibahas pada pertemuan selanjutnya. Data yang telah tersusun dalam  struktur data BST juga dapat dicari dengan mudah dan memiliki rata-rata kompleksitas sebesar O(log n), namun membutuhkan waktu sebesar O(...
    Baca selengkapnya