Heap & Tries

Heap

Heap adalah struktur data berbasis tree dimana merupakan jenis complete binary tree. Heap dibagi menjadi 3 yaitu :

1. Min - Heap : Dalam Min-Heap key yang ada di node root harus paling kecil di antara key yang ada di semua child itu. Properti yang sama harus benar secara rekursif untuk semua sub-tree di binary tree itu.

2. Max - Heap : Dalam Max-Heap key yang ada di node root harus paling besar di antara kunci yang ada di semua child itu. Properti yang sama harus benar secara rekursif untuk semua sub-tree di binary tree itu.

3. Min-Max Heap : adalah Complete Binary Tree yang berisi level min (atau genap) dan max (atau ganjil) bergantian.

Implementasi Heap menggunakan Array :

1. Array dimulai dengan indeks 1.

2. Rumus umum aplikasi heap dengan array adalah (x adalah current node) :

- Parent = x/2

- Left Child = x*2

- Right Child = (x*2)+1

Min-Heap Insertion

1. Pertama meningkatkan ukuran heap oleh 1, sehingga dapat menyimpan elemen baru.

2. Masukkan elemen baru di akhir Heap.

3. Elemen yang baru disisipkan ini dapat merusak properti Heap untuk orang tuanya. Jadi, untuk menjaga properti Heap, heapify elemen yang baru disisipkan ini dengan pendekatan bottom-up / Heapify Up/ Upheap.

Min-Heap Deletion 

1. Ganti root atau elemen yang akan dihapus oleh elemen terakhir.

2. Hapus elemen terakhir dari Heap.

3. Karena, elemen terakhir sekarang ditempatkan pada posisi node root. Jadi, mungkin tidak mengikuti properti heap. Oleh karena itu, heapify node terakhir yang ditempatkan di posisi root (Down Heap / Heapify Down).

Max-Heap Insertion

Dalam memasukkan data ke dalam Max-Heap, yang perlu dilakukan adalah selalu memeriksa apakah node yang akan dimasukkan sudah lebih kecil dibandingkan parentnya.

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

Begitu seterusnya sampai rootnya merupakan data paling besar.

Max-Heap Deletion

Apabila yang ingin dihapus adalah rootnya maka yang perlu dilakukan adalah menggantikan root dengan menggunakan node paling terakhir dari tree. Jika root masih lebih kecil daripada childnya, maka swap root dengan childnya. Begitu seterusnya sampai data di root adalah angka terbesar.

Min-Max Heap

Untuk Insertion dan Deletion dalam Min-Max Heap memiliki cara yang sama dengan Min heap dan Max heap, yang membedakan adalah baris yang min level dibandingkan dengan baris yang min level. Sedangkan baris yang max level dibandingkan dengan max level. 

Tries

Tries adalah tree yang dilakukan untuk menyimpan array asosiatif.

Properti pada tries :

1. Setiap Vertex / node mempresentasikan 1 huruf.

2. Root mempresentasikan karakter kosong.