Skip to main content

Heap & Tries

Heap 
Heap adalah suatu tree yang terdiri dari 3, yaitu Min Heap, Max Heap, dan Min-Max Heap. Heap juga berguna untuk membuat Priority Queue.

Ciri - ciri dari heap adalah :
- Setiap parent mempunyai maksimal 2 child
- Root dari heap berupa angka maksimal / minimal dari tree tersebut
- Berbeda dengan tree lain, heap menyimpan data-datanya di dalam array
- Index array di heap dimulai dari 1 untuk memudahkan ketika mencari parent dari child
- Setiap angka baru yang dimasukkan akan berada pada index terakhir yang akan dibandingkan dengan parentnya

Rumus untuk mencari parent di heap adalah :
Parent_index = index/2
Leftchild_index = index * 2
Rightchild_index = index*2+1

1. Min Heap
Min Heap adalah heap yang dimana rootnya adalah angka minimum dari heap itu sendiri.
Contoh Insertion :

Contoh Deletion :


2. Max Heap
Max Heap adalah kebalikan dari min heap. Max heap adalah sebuah heap yang dimana rootnya adalah angka maksimum dari heap itu sendiri.
Contoh Insertion :
Contoh Deletion :



3. Min-Max Heap
Min-Max Heap adalah sebuah heap yang terdiri dari level-level yang setiap levelnya itu berbeda.
Level genap di heap ini adalah berupa angka min dan level ganjil terdapat angka max.
Angka terkecil dari heap berada di array pertama,
Angka terbesar dari heap berada di array kedua atau ketiga.


Tries
Biasanya di tree pada umumnya, tries menyimpan dalam bentuk karakter. Tries bisa mempunyai anak lebih dari 2. Biasa digunakan untuk auto-complete / searching, bubble words, list/set/collection
misalnya space,spaces,spade,speak,speaker,speakers, dll
Maka kita gak perlu simpan per katanya, melainkan per karakter.

Comments

Post a Comment

Popular posts from this blog

Binary Search Tree

Binary Search Tree        -         Pengertian       Binary search tree (BST) adalah sebuah data struktur yang digunakan untuk mempercepat        searching, sorting, insertion dan deletion.       BST juga dikenal sebagai binary tree yang sudah disortir       Untuk sebuah node x dari BST : è Value di subtree kiri lebih kecil dari value dalam x è Value di subtree kanan lebih besar dari value dalam x       -         Binary search tree operations       BST mempunyai beberapa operasi : è Search(x) : untuk mencari key x di dalam BST Misalnya kita ingin mencari key x : o    Pertama kita mulai dari root o    Jika root adalah x maka proses selesai o    Jika x lebih kecil dari key root maka dilakukan searching secara rekursif di subtree sebelah kiri, be...
Post a Comment
Read more

Hashing Table & Binary Tree

   1.       Hashing and Hash Table ·         Hashing Hashing adalah sebuah teknik untuk menyimpan data   dengan menggunakan index (key) dari string tersebut. Fungsi hashing adalah untuk mendapat index (key) untuk menentukan lokasi data. Contoh Hashing : Misalkan kita ingin menyimpan 5 data string : “define”,”float”,”exp”,”char”,”atan” ke dalam hash table dengan size 26. Hash function yang kita gunakan adalah mengubah karakter pertama dalam string tersebut menjadi angka antara 0 sampai 25. Hasilnya : - define “d” = 3 - float “f” =   5 - exp “e” = 4 - char “c” = 2 - atan “a” = 0                ·         Hash Table Hash table adalah sebuah tabel / array dimana kita menyimpan string / data kita. Index dari tabel adalah hashed key, sedangkan value (isi) di dalamnya adalah value dari data k...
Post a Comment
Read more