-

Heap and Tries

Heap sort adalah sebuah metode sorting (pengurutan) angka pada sebuah array, yaitu dengan cara memvisualisasikan sebuah array menjadi sebuah binary tree yang nantinya pada binary tree tersebut nilai pada masing-masing index array akan diurutkan, dimana dimulai dari index 1.

Heap memiliki 3 jenis yaitu:

1. Min Heap

Min-heap adalah  dimana nilai terkecil berada di node root dan setiap child node memiliki nilai yang lebih besar dari nilai yang dimiliki parent nodenya. Pada pengerjaan simulasi min-heap menggunakan pengecekan up-heap atau heapify-up. Node terbaru yang diinput akan berada diposisi index terakhir yang kosong setelah yang node sudah terisi. Melakukan pengerjaan dimulai cek semua parent harus lebih kecil daripada child, apabila parent lebih besar dari child maka akan dilakukan swap. Hal ini akan dilakukan pengecekan hingga ke rootnya. Apabila ingin mendelete node maka pasti yang didelete adalah root lebih dahulu yang akan diganti dengan angka yang ada diindex terakhir. Setelah itu dilakukan pengecekan dengan down-heap atau heapify-down. Melakukan pengecekan dengan membandingkan root dengan kedua anaknya dan mengambil angka yang paling kecil dari kedua anaknya untuk penganti sebagai rootnya sehingga dilakukan swap. Hal ini akan dilakukan pengecekan hingga index terakhir secara keseluruhan. Contoh insert dan delete pada min-heap ( latihan saya saat kelas kecil ) :

Parent = myIdx / 2;
Left child = myIdx * 2;
Right child = (myIdx*2)+1;




2. Max Heap

Max-heap adalah kondisi heap tree yang memiliki nilai tertinggi berada di node root dan setiap child node memiliki nilai yang lebih kecil dari nilai yang dimiliki parent nodenya. Pada pengerjaan simulasi max-heap menggunakan pengecekan up-heap atau heapify-up. Node terbaru yang diinput akan berada diposisi index terakhir yang kosong setelah yang node sudah terisi. Melakukan pengerjaan dimulai cek semua parent harus lebih besar daripada child, apabila parent lebih kecil dari child maka akan dilakukan swap. Hal ini akan dilakukan pengecekan hingga ke rootnya. Apabila ingin mendelete node maka pasti yang didelete adalah root lebih dahulu yang akan diganti dengan angka yang ada diindex terakhir. Setelah itu dilakukan pengecekan dengan down-heap atau heapify-down. Melakukan pengecekan dengan membandingkan root dengan kedua anaknya dan mengambil angka yang paling besar dari kedua anaknya untuk penganti sebagai rootnya sehingga dilakukan swap. Hal ini akan dilakukan pengecekan hingga index terakhir secara keseluruhan. Contoh insert dan delete pada min-heap ( latihan saya saat kelas kecil ) :




Tries


Tries sama saja dengan tree, anaknya bisa banian tetapi hanya digunakan untuk bentuk character atau string. Tries atau prefix tree adalah suatu pohon struktur data yang terurut yang menyimpan data array, biasanya string. Kata tries diambil dari kata RETRIEVAL, karena tries dapat menemukan kata tunggal dalam kamus dengan hanya awalan katanya saja.

Tries sudah diterapkan ke banyak hal dalam kehidupan sehari-hari, contohnya pada web browser. suatu web browser dapat mengira atau mensugestikan kata-kata yang mungkin kita maksud saat kita mengetik huruf pertamanya saja. (autocomplete)

Tries adalah suatu tree dimana setiap vertex/pathnya menggambarkan suatu kata, rootnya kosong gambarannya :
*
gambar tersebut menunjukan kata : ALGO, API, BOM, BOS, BOSAN, BOR
Berikut adalah code tries dan min-heap yang diberikan oleh assisten dosen kelas kecil:
Tries:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<ctype.h>

#define ALPHABET_SIZE 26
#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) 
#define CHAR_TO_INDEX(c) ((int)tolower(c) - (int)'a') 

struct Character{
struct Character *children[ALPHABET_SIZE];
bool isEndOfWord;
};

struct Character *newNode() 
{ 
    struct Character *curr = NULL; 
  
    curr = (struct Character *)malloc(sizeof(struct Character)); 

    curr->isEndOfWord = false; 
  
    for (int i = 0; i < ALPHABET_SIZE; i++) 
        curr->children[i] = NULL; 
  
    return curr; 
} 

void insert(struct Character *root, const char *key) 
{ 
    int level; 
    int length = strlen(key); 
    int index; 
  
    struct Character *pointer = root; 
  
    for (level = 0; level < length; level++) 
    { 
        index = CHAR_TO_INDEX(key[level]); 
        if (pointer->children[index] == NULL) 
            pointer->children[index] = newNode(); 
  
        pointer = pointer->children[index]; 
    } 
  
    pointer->isEndOfWord = true; 
} 

bool search(struct Character *root, const char *key) 
{ 
    int level; 
    int length = strlen(key); 
    int index; 
    struct Character *pointer = root; 
    
    for (level = 0; level < length; level++) 
    { 
        index = CHAR_TO_INDEX(key[level]); 
  
        if (pointer->children[index] == NULL) 
            return false; 
  
        pointer = pointer->children[index]; 
    } 
  
    return pointer->isEndOfWord; 
} 

int main(){
char keys[][8] = {"there", "was", "a", "farmer", "that", "has", "big", "farm"}; 
char output[][32] = {"Not present in trie", "Present in trie"};
struct Character *root = newNode(); 
    
int i; 
    for (i = 0; i < ARRAY_SIZE(keys); i++) 
        insert(root, keys[i]); 
    
   
    printf("%s -> %s\n", "there",output[search(root, "there")]);
    printf("%s -> %s\n", "bomb",output[search(root, "bomb")]);
    printf("%s -> %s\n", "that",output[search(root, "that")]);
    printf("%s -> %s\n", "shark",output[search(root, "shark")]);
    printf("%s -> %s\n", "shop",output[search(root, "shop")]);
    printf("%s -> %s\n", "farmer",output[search(root, "farmer")]);
    printf("%s -> %s\n", "farme",output[search(root, "farme")]);
    
return 0;
}

Min-heap:
#include<stdio.h>
#include<stdlib.h>

/*
        0
   1          2
 3   4     5     6
7 8 9 10 11 12 13 14
*/

int arr[1000] = {NULL};
int totalData = -1;

void checkParent(int index){
int parentIndex = (index - 1) / 2;
if(index > 0 && arr[parentIndex] > arr[index]){
int temp = arr[parentIndex];
arr[parentIndex] = arr[index];
arr[index] = temp;
checkParent(parentIndex);
}
}

void insert(int key){
totalData += 1;
arr[totalData] = key;
checkParent(totalData);
}

void checkChild(int index){
int left = (index * 2) + 1;
int right = (index * 2) + 2;
if(left > totalData){
//pass
}
else if(right > totalData){
if(arr[index] > arr[left]){
int temp = arr[index];
arr[index] = arr[left];
arr[left] = temp;
checkChild(left);
}
}
else{
if(arr[left] > arr[right]){
if(arr[index] > arr[right]){
int temp = arr[index];
arr[index] = arr[right];
arr[right] = temp;
checkChild(right);
}
}
else{
if(arr[index] > arr[left]){
int temp = arr[index];
arr[index] = arr[left];
arr[left] = temp;
checkChild(left);
}
}
}
}

void popRoot(){
if(totalData == 0){
arr[0] = NULL;
totalData--;
}
if(totalData > 0){
arr[0] = arr[totalData];
checkChild(0);
totalData--;
}
}

void print(){
for(int i =0; i <= totalData; i++){
printf("%d \t", arr[i]);
}
puts("");
}

int main(){
insert(10);
insert(12);
insert(15);
insert(3);
insert(6);
insert(2);
print();
popRoot();
print();
popRoot();
print();
popRoot();
print();
return 0;
}

Nama : Dewi Mutiara
NIM : 2301887830

Komentar

Posting Komentar

Postingan populer dari blog ini

-
Gambar
Hashing table & Binary Tree Hashing Hash Table Hash Function Collision  Tree Concept Binary Tree Concept Type of Binary Tree Property of Binary Tree Expression Tree Concept Threaded Binary Tree Concept 1. Hashing Hashing adalah proses menghasilkan data keluaran (output data) yang panjangnya tetap dan sama, dari data masukan (input data) yang panjangnya berbeda-beda. Hashing adalah bentuk akses data yang efisien secara komputasi dan ruang penyimpanan yang menghindari waktu akses non-linear dari daftar dan pohon terstruktur yang dipesan dan tidak tersusun, dan persyaratan penyimpanan yang sering eksponensial untuk akses langsung ruang negara dari kunci besar atau panjang variabel. 2. Hash Table Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.  Keunggulan dari struktur hash ta...
Baca selengkapnya
-
Gambar
Linked list dalam Data Structure Linked List saling terhubung dengan bantuan variabel pointer. Masing-masing data dalam Linked List disebut dengan node (simpul) yang menempati alokasi memori secara dinamis dan biasanya berupa struct yang terdiri dari beberapa field. Single  : artinya field pointer-nya hanya satu buah saja dan satu arah serta pada akhir node, pointernya menunjuk NULL. Linked List  : artinya node-node tersebut saling terhubung satu sama lain. Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya, dan juga memiliki field yang berisi data. Node terakhir akan menunjuk ke NULL yang akan digunakan sebagai kondisi berhenti pada saat pembacaan isi linked list. J enis Single LinkList : Single linked list dengan HEAD Single linked list dengan HEAD dan TAIL  Pembuatan Single Linked List  Keyword new gunanya untuk mempersiapkan sebuah node baru berserta alokasi memorinya, kemudian node t...
Baca selengkapnya
-
Gambar
AVL TREE AVL Tree hampir sama dengan BST atau yang sering kita sebut Binary Search Tree. Dalam AVL Tree memiliki syarat atau ciri khas yaitu memiliki perbedaan tinggi/ level maksimal 1 antara anak kiri dan anak kanan. AVL Tree digunakan untuk membuat balance saat sedang lakukan penambahan node baru atau menghapus sebuah node. Kita dapat mencari balance factor dengan cara menghitung selisih panjang anak kiri dikurang dengan panjang anak kanan. Apabila tidak memiliki anak dianggap 0. Insert node Untuk menambahkan sebuah node baru ke dalam tree harus dilakukan pengecekan dimulai dari ujung leaf hingga root. Node pertama yang merusak atau memiliki balance factor lebih dari 1 maka akan diseimbangkan dengan Single Rotation atau Double rotation. Single rotation Single rotation dilakukan sekali ketika kondisi AVL Tree saat ditambahkan node baru dan posisi node tersebut seperti gambar dibawah ini: Gambar yang kiri tidak balance karena balance factor dari 30 lebih dari 1 s...
Baca selengkapnya