Heaps & Tries

 1. Definisi. 

 Heap adalah bagian dari memori yang terorganisasi untuk dapat melayani alokasi memori secara dinamis. Heap merupakan struktur data berbasis pohon khusus di mana pohon itu adalah pohon biner yang lengkap. 

2. Max Heap

Dalam Max-Heap kunci yang ada di simpul akar harus paling besar di antara kunci yang ada di semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner tersebut.

Cara insert:

a. memasukan data dengan konsep array, sehingga kekanan terus lalu kebawah. Elemen terakhir akan masuk ke index terakhir dan menjadi anak paling kanan dan paling bawah.

b. data yang di insert akan dibandingkan dengan parent jika lebih besar maka akan swap. Bandingkan terus sampai data baru lebih kecil dari parent.

Cara delete:

a. jika elemen terkecil terletak di root maka yang akan dihapus adalah element terbesarnya.

b. Root yang dihapus kemudian digantikan oleh data terakhir di nodenya kemudian data tersebut  di down heap max sampai node lebih besar dari child node.

3. Min Heap

Dalam Min-Heap kunci yang ada di simpul akar harus minimum di antara kunci yang ada di semua anak-anak itu. Properti yang sama harus benar secara rekursif untuk semua sub-pohon di Pohon Biner itu.

Cara insert :

a. memasukkan data dengan konsep array, sehingga kekanan terus lalu kebawah. Elemen terakhir akan masuk ke index terakhir dan menjadi anak paling kanan dan paling bawah.

b. data yang sudah dimasukkan lalu dibandingkan dengan parent. Jika data tersebut lebih kecil makan akan di swap. Bandingkan terus sampai data baru lebih besar dari parent.

Cara delete :

a. jika elemen terkecil terletak di root maka yang akan dihapus adalah elemen terkecil.

b. root yang sudah dihapus kemudian digantikan oleh data terakhir pada nodenya. 

Lalu data tersebut di down heap min sampai node lebih kecil dari child node.

4. Min-Max Heap

Min-Max Heap adalah heap yang tiap level selalu bergantian Min-Max-Min-Max. dalam Min-Max dan setiap heap selalu di awali dengan min heap. Min- Max Heap berguna untuk langsung menemukan nilai min dan max dalam 1 heap saja. Pada level min semakin kebawah maka nilainya semakin besar. Pada level max  semakin kebawah maka nilainya semakin kecil. Kondisi heap selalu bergantian, yaitu level minimal dan maksimal. 

-Setiap elemen pada level genap atau ganjil lebih kecil dari semua anak-anaknya (level min).

Cara insert :

a. proses node baru akan dilakukan akan dipengaruhi oleh lokasi node tersebut.

b. jika node baru berada di level min makan akan dibandingkan dengan parentnya. Jika   parent lebih kecil dari node baru maka swap dan up heap max dari parent dan akan dibandingkan dengan grandparent dari posisi node baru setelah swap. Jika parent lebih besar dari node baru, up heap min dari posisi node baru akan dibandingkan dengan grandparent dari posisi node baru.

-Setiap elemen pada level ganjil atau genap lebih besar dari semua anak-anaknya (level maks).

Cara insert :

a. proses node baru akan dilakukan dipengaruhi oleh lokasi node baru tersebut.

b. jika node baru berada di level max, maka akan dibandingkan dengan parentnya. Jika parent lebih besar dari node baru maka swap dan up heap min dari parentnya akan dibandingkan dengan grandparentnya dari posisis node baru setelah swap. Jika parent lebih kecil dari node baru up heap  max dari posisi node baru akan dibandingkan dengan grandparent dari posos node baru.

5. Implementasi.

Heap tree bermanfaat untuk mengimplementasikan priority queue. Priority queue merupakan struktur data yang sifatnya sangat mirip dengan antrian, yaitu penghapusan/pengurangan anggota selalu dilakukan pada anggota antrian yang terdepan dan penambahan anggota selalu dilakukan dari belakang antrian berdasarkan prioritas anggota tersebut (anggota yang memiliki prioritas lebih besar selalu berada di depan anggota yang memiliki prioritas lebih rendah). 

Heap tree memerlukan beberapa metoda sebagai berikut: 

a. Metoda untuk menginisialisasi suatu CBT (Complete Binary Tree) A secara umum menjadi heap.

b. Metoda untuk mengambil data paling besar, yaitu root dari heap.

c.  Metoda untuk menambahkan satu key baru ke dalam heap tree.

d. Metoda untuk menyusun ulang menjadi heap tree kembali setelah dilakukan metoda B atau C.

Kriteria yang penting untuk dipenuhi adalah bahwa setiap metoda di atas beroperasi pada tree yang selalu berbentuk CBT (Complete Binary Tree) karena struktur level lebih rendahnya tetap merupakan suatu array.

6. Representasi Alokasi Dinamis Algoritma Pengurutan Heap Sort.

Karakteristik dari algoritma pengurutan heap sort adalah bahwa dalam implementasinya heap sort menggunakan heap tree agar dapat diselesaikan secara heapsort. Oleh karena itu, untuk mengimplementasikan algoritma pengurutan heap sort dalam suatu program aplikasi, dibutuhkan adanya alokasi dinamis dengan menggunakan struktur data tree (pohon). 

Prinsip-prinsip dasar mengenai struktur data tree yang digunakan untuk merealisasikan heap tree adalah sebagai berikut: 

a. Node-node saling berhubungan dengan menggunakan pointer. Pada struktur data tree ini digunakan minimal dua buah pointer pada setiap node, masing-masing untuk menunjuk ke cabang kiri dan cabang kanan dari tree tersebut. Struktur data tree dideklarasikan sebagai berikut: 

Class BinaryTreeNode { 

KeyType Key; 

InfoType Info; 

BinaryTreeNode Left, Right; 

 } 

b. Left dan Right berharga NULL apabila tidak ada lagi cabang pada arah yang bersangkutan. 

c. Struktur dari binary tree, termasuk hubunganhubungan antar-node, secara eksplisit direpresentasikan oleh Left dan Right. Apabila diperlukan penelusuran naik (backtrack), maka hal tersebut dapat dilakukan dengan penelusuran ulang dari root, penggunaan algoritma-algoritma yang bersifat rekursif, atau penggunaan stack.

d. Alternatif lain adalah dengan menambahkan adanya pointer ke parent. Namun hal ini akan mengakibatkan bertambahnya jumlah tahapan pada proses-proses penambahan/penghapusan node.

Algoritma pengurutan heap sort dapat dikategorikan ke dalam algoritma divide and conquer dengan pendekatan pengurutan sulit membagi, mudah menggabung (hard split/easy join) seperti halnya algoritma pengurutan quick sort dan selection sort. Hal ini disebabkan pembagian dilakukan dengan terlebih dahulu menerapkan algoritma metoda heapify sebagai inisialisasi awal untuk mentransformasi suatu Complete Binary Tree (CBT) menjadi heap tree dan pada setiap tahapan diterapkan algoritma metoda reheapify untuk menyusun ulang heap tree.

7. Tries 

Tries adalah tree yang dilakukan untuk menyimpan array asosiatif. Properties yang terdapat di Tries:

-Setiap vertex/node merepresentasikan satu huruf.

-Root merepresentasikan karakter kosong.

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

Struktur data dari tree berututan yang digunakan untuk menyimpan array asosiatif biasanya adalah string. Tries merupakan pohon yang setiap simpulnya mewakili satu kata atau awalan. Root mewakili karakter kosong (‘’). Vertex adalah jarak dari root memiliki awalan yang terkait dengan panjang K. misalkan A dan B adalah dua simpul dari pecobaan. A adalah orangtua dari B, maka B harus memiliki awalan yang terkait dengan A.