HeapSort dan Trie

HeapSort

Heap sort adalah teknik penyortiran berbasis perbandingan yang didasarkan pada struktur data Binary Heap. Ini mirip dengan pemilihan jenis di mana kita pertama kali menemukan elemen maksimum dan menempatkan elemen maksimum di akhir. Kami ulangi proses yang sama untuk elemen yang tersisa.

Karena Binary Heap adalah Binary Tree lengkap, itu dapat dengan mudah dipresentasikan sebagai representasi berbasis array dan ruang efisien. Jika simpul induk disimpan pada indeks I, anak kiri dapat dihitung dengan 2*I+1 dan anak kanan dengan 2*I+2 (dengan asumsi indeks dimulai pada 0).

Heap Sort Algorithm untuk mengurutkan dalam urutan yang meningkat:

1. Buat tumpukan maksimum dari data input.

2. Pada titik ini, item terbesar disimpan di root heap. Ganti dengan item terakhir heap diikuti dengan mengurangi ukuran heap oleh 1. Akhirnya, heapify akar pohon.

3. Ulangi langkah di atas sementara tumpukan lebih besar dari 1.

Contoh Codingan dalam bahasa C:

// C++ program for implementation of Heap Sort

#include <iostream>

  

using namespace std;

  

// To heapify a subtree rooted with node i which is

// an index in arr[]. n is size of heap

void heapify(int arr[], int n, int i)

{

    int largest = i; // Initialize largest as root

    int l = 2*i + 1; // left = 2*i + 1

    int r = 2*i + 2; // right = 2*i + 2

  

    // If left child is larger than root

    if (l < n && arr[l] > arr[largest])

        largest = l;

  

    // If right child is larger than largest so far

    if (r < n && arr[r] > arr[largest])

        largest = r;

  

    // If largest is not root

    if (largest != i)

    {

        swap(arr[i], arr[largest]);

  

        // Recursively heapify the affected sub-tree

        heapify(arr, n, largest);

    }

}

  

// main function to do heap sort

void heapSort(int arr[], int n)

{

    // Build heap (rearrange array)

    for (int i = n / 2 - 1; i >= 0; i--)

        heapify(arr, n, i);

  

    // One by one extract an element from heap

    for (int i=n-1; i>0; i--)

    {

        // Move current root to end

        swap(arr[0], arr[i]);

  

        // call max heapify on the reduced heap

        heapify(arr, i, 0);

    }

}

  

/* A utility function to print array of size n */

void printArray(int arr[], int n)

{

    for (int i=0; i<n; ++i)

        cout << arr[i] << " ";

    cout << "\n";

}

  

// Driver program

int main()

{

    int arr[] = {12, 11, 13, 5, 6, 7};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    heapSort(arr, n);

  

    cout << "Sorted array is \n";

    printArray(arr, n);

}

Trie

Trie adalah struktur data pencarian informasi yang efisien. Menggunakan Trie, kompleksitas pencarian dapat dibawa ke batas optimal (panjang kunci). Jika kita menyimpan kunci dalam pohon pencarian biner, BST yang seimbang akan membutuhkan waktu yang proporsional dengan M*log N, di mana M adalah panjang string maksimum dan N adalah jumlah kunci dalam pohon. Dengan menggunakan Trie, kita dapat mencari kunci dalam waktu O (M). Namun penalti ada pada persyaratan penyimpanan Trie.

Memasuukkan kunci ke Trie adalah pendekatan sederhana. Setiap karakter kunci input dimasukkan sebagai simpul Trie individual. Perhatikan bahwa anak-anak adalha array pointer (atau referensi) ke node trie level berikutnya. Karakter kunci bertindak sebagai  indeks ke dalam array anak-anak. 

Jika input adalah  baru atau ekstensi dari kunci yang ada, kita perlu membangun simpul kunci yang tidak ada, dan menandai akhir kata untuk simpul terakhir.

Jika kunci input adalah awalan dari kunci yang ada di Trie, kami cukup menandai simpul terakhir kunci sebagai akhir kata. Panjang kunci menentukan kedalaman Trie. 

Contoh Coding Trie dalam C :

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

}




Sekian post blognya sampai di sini, semoga bermanfaat!