Heap & Tries

Materi data structure 12 Mei 2020

Heap 

heap merupakan sebuah Complete Binary Tree yang memenuhi persyaratan heap.

secara umum heap terbagi menajdi 2 yaitu: Min Heap dan Max Heap.

Min heap merupakan heap dengan nilai parent yang lebih kecil dari pada childrennya.

Max heap merupakan heap dengan nilai parent yang lebih besar dari pada childrennya

contohnya :

kegunaan dari heap yaitu Heap itu gunanya untuk menemukan nilai max untuk max heap, dan min untuk min heap. dan ini sangat berguna pada saat membuat Priority Queue.

Heaps are usually implemented in an array. And root is sorted at index 1

example:

cara untuk mencari parent sm child tinggal masukin rumus:
Index_Parent=Index/2;
Index_Child_Kiri=Index*2;
Index_Child_kanan=Index*2+1;

Insertion 

untuk insertion baik pada min heap dan max heap sama saja, akan tetapi hanya berbeda pada tanda penunjuk lebih besar atau lebih kecilnya saja.

insertion pada min heap

Saat sebuah data baru dimasukkan dalam heap, maka data langsung ditempatkan di index terakhir dalam heap. Setelah itu, data di-upheap. Maksudnya, data dibandingkan dengan parentnya. Bila lebih kecil, maka swap dengan parentnya. Hal ini dilakukan sampai data tersebut lebih besar dari parentnya.

contoh:

pada tahap dibawah ini angka 1 dimasukan ke dalam heap. maka data tersebut akan di up-heap

ternyata 1<51. Maka, 1 dan 51 di swap. Begitu pula dengan saat 1 dibandingkan dengan 50 dan dengan 2.

maka tampilan akhir dari heap kita akan menjadi sebagai berikut

untuk insertion pada max heap kebalikan dari min heap tetapi caranya sama saja hanya dibalik pembadingnya saja

Deletion

Jika dalam insertion dipakai Upheap, maka dalam deletion dipakai Downheap. Deletion dalam heap otomatis menghapus node root dari heap. Jadi, delete min dalam min heap dan delete max dalam max heap.

Dalam deletion, node paling akhir langsung menggantikan root yang didelete. Kemudian, node tersebut langsung di downheap sampai ke posisinya.

contoh:

Node 1 pada gambar dibawah ini yang berperan sebagai root langsung dihapus dalam deletion.

node 51 sebagai data paling akhir langsung naik menjadi root . Node tersebut akan di-downheap; ditukar dengan min(LeftChild, RightChild) bila node < min(LeftChild, Right Child)

 Sehingga min heap tersebut akan menjadi seperti gambar disamping.

Tries

Kata trie adalah infiks dari kata "retrieval" karena trie dapat menemukan satu kata dalam kamus dengan hanya awalan kata. Gagasan utama dari struktur data trie terdiri dari bagian-bagian berikut:

•Tries is a tree where each vertex represents a single word or a prefix.

•The root represents an empty character (‘’).

•A vertex that are k edges of distance from the root have an associated prefix of length k.

•Let a and b be two vertices of the tries and assume a is a direct parent of b, then b must have an associated prefix of a.

Contoh dari tries sebagai berikut:

contoh dari tries yang memuat kata :  “tree”, “trie”, “algo”, “assoc”, “all”, and “also.”

NAMA : Timothy Gilbert
NIM : 2301851036
Kelas Besar : CB01
Kelas Kecil : LK01

sumber:

ppt Binus pert 12 mei

http://apalah-ini-itu.blogspot.com/2011/06/heap.html
https://www.topcoder.com/community/competitive-programming/tutorials/using-tries/