Heaps and Tries

Heap

Heap adalah pohon complete binary tree biner yang berdasarkan memenuhi properti heap. Property heaps antara lain :

Min Heap
Setiap node lebih kecil dari masing-masing childnya
Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf node

           10                     10
         /    \                /      \ 
       20      100            15        30 
      /                      /  \      /  \
    30                     40    50  100   40


Max Heap
Setiap node lebih besar dari masing-masing childnya
Root merupakan node paling besar, sedangkan node terkecil terletak pada leaf node

Image result for Max Heap


Min-Max Heap
Heap dengan Min heap pada level ganjil dan Max heap pada level genap

Image result for Min max heap


Heap dapat diimplementasi dengan array maupun dengan linked list. Aplikasi heap adalah sebagai berikut:

Priority Queue

  1. Selection algorithm
  2. Dijkstra's Algorithm
  3. Prim Algorithm

Implementasi heap menggunakan array :

  • Array dimulai dengan indeks ke 1
  • Rumus umum aplikasi heap dengan array (x adalah current node):
    • Parent(x): x/2
    • Left-child(x): 2*x
    • Right-Child(x): 2*x+1

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.

Pengaplikasian Tries
Tries digunakan untuk search dalam sebuah web browser untuk menunjukkan auto-complete saat mencari, contohnya setelah mengetik "goo", system akan menunjukkan beberapa pilihan yang mungkin ingin kita cari seperti "google".

Comments

Post a Comment

Popular posts from this blog

Hashing table & Binary Tree

Image
Hashing Table Hashing adalah sebuah cara untuk mengetahui objek secara spesifik dari kumpulan objek yg mirip. Sedangkan 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. Operasi pada hash table: insert: diberikan sebuah key dan nilai, insert nilai dalam tabel find: diberikan sebuah key, temukan nilai yang berhubungan dengan key remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu Contoh deklarasi hash table dalam coding: HASHTBL *hashtbl_create(hash_size size, hash_size (*hashfunc)(const char *)) { HASHTBL *hashtbl; if(!(hashtbl=malloc(sizeof(HASHTBL)))) return NULL; free(hashtbl); return NULL; } hashtbl->size=size; if(hashfunc) hashtbl->hashfunc=hash
Read more

Laporan Akhir Mata Kuliah Human and Computer Interaction Aplikasi Predical

Image
LAPORAN AKHIR MATA KULIAH HUMAN AND COMPUTER INTERACTION APLIKASI PREDICAL   Disusun oleh Elbert Adiwijanto 2301881171 Georgius Andrian Halim 2301854315 Stanley Jonathan 2301893820 1. Pendahuluan 1.1. Latar Belakang Permasalahan utama yang mendorong kami untuk mendesain aplikasi ini berawal dari jumlah kasus misdiagnosis penyakit jantung dan angka kejadian penyakit jantung yang semakin meningkat. Berdasarkan hasil observasi kami, Organisasi Kesehatan Dunia (WHO) menyatakan bahwa terdapat lebih dari 17.9 juta orang di seluruh dunia yang meninggal setiap tahunnya, dimana 32% kematian di dunia diakibatkan oleh penyakit jantung dan pembuluh darah. Lebih lanjut, berdasarkan salah satu contoh kasus misdiagnosis di Indonesia, di mana terdapat seorang gadis yang mengalami misdiagnosis antara penyakit flu dengan penyakit jantung, kasus ini menguatkan fakta bahwa penyakit jantung ini bisa diterima dari yang muda hingga yang tua dan juga ternyata dokter ma
Read more

FINAL SUMMARY

Image
LINKED LIST 1. Circular Single Linked List Di circular single linked list, node terakhir (tail) berisikan sebuah pointer yang terhubung ke node pertama (head), sehingga membentuk sebuah sirkuit, yang berarti tidak ada awal maupun akhir dan tidak ada NULL setelah node manapun, karena seperti contoh gambar dibawah, setelah node 3 adalah node 1. Gambar berikut adalah contoh dari circular single linked list: 2. Doubly Linked List Berbeda dengan circular single linked list, doubly linked list ini tidak membentuk sebuah sirkuit. Di setiap node ada sebuah pointer yang menunjuk ke node sebelum dan setelahnya. Dalam doubly linked list ini, setiap node berisikan 3 bagian: node data, pointer ke node berikutnya, dan pointer ke node sebelumnya. Gambar berikut adalah contoh dari doubly linked list: 3. Circular Doubly Linked List Sesuai dengan namanya, circular doubly linked list merupakan gabungan dari circular single linked list dan
Read more