Heap and Tries

HEAP
Heap adalah struktur data tree yang merupakan complete binary tree (bukan binary search tree). Heap memiliki beberapa properties yaitu :

1. Min Heap

• Setiap node lebih kecil dari masing-masing childnya.
• Root memiliki nilai terkecil. Nilai terbesar terletak di leaf node.

 

2. Max Heap

• Setiap node lebih besar daripada childnya.
• Root memiliki nilai terbesar. Nilai terkecil terletak di leaf node.

3. Min-Max Heap

• Heap dengan Min Heap pada level genap dan Max Heap pada level ganjil.

Heap dapat diimplementasikan dengan array juga linked list.

Aplikasi pada heap :

1. Priority Queue

- Selection Algorithm

- Dijkstra's Algorithm

- Prim Algorithm

2. Heap Sort

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

Min Heap (Ascending Order) :

- Insertion pada Min Heap

1. Insert node selalu berurutan dari level paling rendah dengan urutan kiri ke kanan.

2. New node selalu menjadi leaf node.

3. Sesuaikan sesuai properti heap secara rekursif.

- Deletion pada Min Heap

1. Node yang dihapus selalu root karena node yang paling kecil, lalu diganti dengan node yang paling terakhir di insert.

2. Sesuaikan dengan properti heap secara rekursif.

Hapus node 7

7 diganti dengan elemen terakhir

Max Heap (Descending Order) :

- Insertion pada Max Heap

1. Periksa apakah node yang akan dimasukkan sudah lebih kecil dibandingkan parentnya.

2. Apabila node yang dimasukkan lebih besar daripada parentnya, maka swap posisi node tersebut dengan parentnya.

3. Begitu seterusnya sampai root merupakan data paling besar.

- Deletion pada Max Heap

1. Jika ingin menghapus root maka yang perlu dilakukan adalah menggantikan root dengan menggunakan node paling terakhir dari tree.

2. Jika root masih lebih kecil daripada child-nya, maka swap root dengan child-nya.

3. Begitu seterusnya sampai data di root merupakan data terbesar.

Min-Max Heap

- Insertion pada Min-Max Heap

Insert node sesuai urutan, lalu cek upheap lalu sesuaikan dengan properties level. Umumnya dilakukan penyesuaian rekursif dengan urutan sebagai berikut:

1. Parent

2. Grand Parent

- Deletion pada Min-Max Heap

Deletion selalu dilakukan pada root, lalu sesuaikan dengan downheap sesuai properties. Umumnya dilakukan penyesuaian secara rekursif dengan urutan sebagai berikut:

1. Grand child

2. Child (grand child disesuaikan dengan parentnya)

TRIES

- Tries adalah binary tree yang dilakukan untuk menyimpan array asosiatif.

- Properties pada tries :

1. Setiap node merepresentasikan satu huruf.

2. Root selalu merepresentasikan node kosong.

- Aplikasi pada trees adalah fitur auto complete yang ada pada browser.

~Thankyou~