Data Structure (Pertemuan 8)

HEAP

Heap adalah salah satu data structure yang berbentuk tree dan berbeda dengan binary search tree (BST).

Jenis-jenis dari heap adalah Max-Heap, Min-Heap, dan Min-Max Heap.

MAX HEAP

Node paling atas berisi value angka yang paling besar dari anak-anak dan keturunannya.

Anak dari suatu node harus lebih kecil daripada orang tuanya, jika tidak maka harus dilakukan rotasi.

MIN HEAP

Node paling atas berisi value angka yang paling kecil dari anak-anak dan keturunannya.

Anak dari suatu node harus lebih besar daripada orang tuanya, jika tidak maka harus dilakukan rotasi.

MIN-MAX HEAP

Min-max heap tersusun dari tree yang tiap levelnya memiliki heap yang berbeda (max atau min).

Pada level 0 (paling atas) adalah min heap, pada level 1 max heap dan seterusnya.

INSERT

Heap di insert / disusun dari atas ke bawa dan dari kiri ke kanan.

Pada gambar di bawah, terdapat salah satu contoh insert angka 15 pada max heap.

Setelah angka 15 di insert, karena heap adalah max heap maka dia harus cek ke parentnya apakah angka 15 tersebut lebih besar daripada parentnya. Jika ya, maka keduanya harus bertukar tempat. Begitu seterusnya sampai angka 15 lebih kecil daripada parentnya atau angka 15 telah sampai di level 0.

TRIES

Tries adalah struktur data yang berbentuk tree dan digunakan untuk mencari sebuah kata (misalnya dalam sebuah search engine).

Tries berasal dari kata Retrieval .

HASHING

Hashing adalah salah satu struktur data yang merupakan transformasi dari string untuk mengambil nilai length terpendek dalam string.

Tujuan dari Hashing adalah untuk mempercepat pencarian data yang sudah tersimpan sebelumnya.