DATA STRUCT
Binary Heap
Binary Heap adalah Complete Binary Tree di mana item disimpan dalam urutan khusus sedemikian sehingga nilai dalam simpul parent lebih besar (atau lebih kecil) dari nilai-nilai dalam dua node child-nya. Yang pertama disebut sebagai max heap dan yang terakhir disebut min heap. Heap dapat diwakili oleh binary tree atau array.
1) Max Heap
Selalu menyimpan nilai maksimum pada simpul root dan setiap simpul induk harus memiliki nilai simpul child yang lebih besar atau sama.
2) Min Heap
Selalu menyimpan nilai minimum pada simpul root itu dan setiap simpul induk harus memiliki nilai yang lebih kecil atau sama dengan nilai simpul child itu.
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.
Contoh di atas menunjukkan dua skenario - satu di mana root adalah elemen terbesar dan kita tidak perlu melakukan apa pun. Dan yang lain di mana root memiliki elemen yang lebih besar sebagai seorang anak dan kami perlu bertukar untuk mempertahankan properti max-heap.
Terdapat sebuah skenario dimana ada lebih dari satu level:
Untuk mempertahankan properti max tree, terus mendorong 2 ke bawah hingga mencapai posisi yang benar.
TRIES
Trie adalah struktur data berupa pohon terurut untuk menyimpan suatu himpunan string dimana setiap node pada tree tersebut mengandung awalan (prefix) yang sama,
karena itulah trie disebut juga tree prefix. Trie sering digunakan pada masalah komputasi yang melibatkan penyimpanan dan pencarian string. Trie memiliki sejumlah keunggulan dibanding struktur data lain untuk memecahkan masalah serupa terutama dalam hal kecepatan dan memori yang digunakan.
Setiap simpul Trie terdiri dari banyak cabang. Setiap cabang mewakili karakter kunci yang memungkinkan. Kita perlu menandai simpul terakhir dari setiap kunci sebagai simpul kata akhir.
Contoh Codingan Tries:
HEAP and TRIES
Binary Heap
Binary Heap adalah Complete Binary Tree di mana item disimpan dalam urutan khusus sedemikian sehingga nilai dalam simpul parent lebih besar (atau lebih kecil) dari nilai-nilai dalam dua node child-nya. Yang pertama disebut sebagai max heap dan yang terakhir disebut min heap. Heap dapat diwakili oleh binary tree atau array.
1) Max Heap
Selalu menyimpan nilai maksimum pada simpul root dan setiap simpul induk harus memiliki nilai simpul child yang lebih besar atau sama.
2) Min Heap
Selalu menyimpan nilai minimum pada simpul root itu dan setiap simpul induk harus memiliki nilai yang lebih kecil atau sama dengan nilai simpul child itu.
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.
Contoh di atas menunjukkan dua skenario - satu di mana root adalah elemen terbesar dan kita tidak perlu melakukan apa pun. Dan yang lain di mana root memiliki elemen yang lebih besar sebagai seorang anak dan kami perlu bertukar untuk mempertahankan properti max-heap.
Terdapat sebuah skenario dimana ada lebih dari satu level:
Untuk mempertahankan properti max tree, terus mendorong 2 ke bawah hingga mencapai posisi yang benar.
TRIES
Trie adalah struktur data berupa pohon terurut untuk menyimpan suatu himpunan string dimana setiap node pada tree tersebut mengandung awalan (prefix) yang sama,
karena itulah trie disebut juga tree prefix. Trie sering digunakan pada masalah komputasi yang melibatkan penyimpanan dan pencarian string. Trie memiliki sejumlah keunggulan dibanding struktur data lain untuk memecahkan masalah serupa terutama dalam hal kecepatan dan memori yang digunakan.
Setiap simpul Trie terdiri dari banyak cabang. Setiap cabang mewakili karakter kunci yang memungkinkan. Kita perlu menandai simpul terakhir dari setiap kunci sebagai simpul kata akhir.
Contoh Codingan Tries:
// Trie node
struct TrieNode
{
struct TrieNode *children[ALPHABET_SIZE]; // isEndOfWord is true if the node
// represents end of a word
bool isEndOfWord;
};Dalam trie, tidak ada node yang menyimpan kunci
yang terkait dengan node tersebut, sebaliknya, posisinya
di pohon menunjukkan kunci apa yang terkait dengannya.
Setiap keturunan dari sebuah node memiliki prefix yang
sama dengan string yang diwakilkan oleh node tersebut,
dan akar menandakan sebuah string kosong.
Comments
Post a Comment