Heap & Tries

Nama: Bryan Frederick

NIM: 2301871984

HEAP

          Jadi, heap ini seperti binary tree tetapi inputannya dari array. Heap ini struktur data yang berbasis pohon biner lengkap dengan properti heap. Ada 3 jenis heap yaitu: min-heap, max-heap, min max - heap.

1. min-heap itu setiap node elemennya lebih kecil dari node elemen anaknya. Jadi, dapat disimpulkan bahwa min-heap pada rootnya pasti selalu yang paling kecil. Heap ini dapat diimplementasikan menggunakan linked list, tetapi jauh lebih mudah menggunakan implementasi dari heap menggunakan array. Heap adalah implementasi efisien dari struktur data antrian prioritas.

find-min: cari elemen terkecil di heap.

masukkan: masukkan elemen baru ke heap.

delete-min: hapus elemen terkecil dari heap.

delete-min juga disebut pop, dan masukkan disebut push.

sumber gambar: https://syncrosyzx.files.wordpress.com/2011/06/arrat.png

sumber gambar:https://syncrosyzx.files.wordpress.com/2011/06/tree6.png

Implementasi Array

• Setiap simpul terkait dengan parentnya, kiri dan kanan pada implementasi array dapat dikomputasi dengan mudah.

• Biarkan indeks simpul saat ini menjadi x.

   • Induk (x) = x / 2

   • Anak kiri (x) = 2 * x

   • Anak kanan (x) = 2 * x + 1

Inilah sebabnya kami menggunakan indeks 1 sebagai root, jika tidak, relasinya tidak akan tampak sesederhana ini.

2.max-heap itu setiap node elemennya lebih besar dari node elemen anaknya. Jadi, konsepnya sama saja dengan min-heap hanya terbalik saja. kalau min heap yang kecil maka max heap yang besar.

3. min max heap. ini seperti gabungan dari kedua heap tetapi bedanya seperti ini, jadi di binary tree kita tau ada levelnya seperti level 1,2 dan 3 atau dikenal dengan ketinggian. nah untuk level 1 misalnya min maka level 2 max.

sumber gambar: https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEisb0tp2iQSZZN0OCmKma_L7zFNrMG_zMyOq95QiSF5E5S5vyIxH3T6V3aAFtH77fneW8GOoRhB3hQ3Nq1uAk8YDtWHo7zyaEocKJ637LE6LSUwPU0grKgA2E9rkc10XX0s6Hw5VZQ5QQc/s1600/Picture3.png

TRIES

kalau heap lebih ke array angka maka tries ini lebih ke array character atau string. dan ini berguna biasanya dalam mencari inisial dan ini akan sangat membantu sekali seperti pembuatan kamus.

sumber gambar: https://i.imgur.com/vdD4dfZ.png

Demikian yang dapat saya sampaikan.

sumber materi binusmaya resources.