Pengertian dan contoh soal pada struktur data heap tree

Heap Adalah struktur data yang berbentuk pohon yang memenuhi sifat-sifat heap yaitu jika B adalah anak dari A, maka nilai yang tersimpan di simpul A lebih besar atau sama dengan nilai yang tersimpan di simpul B.

Jika elemen dengan nilai terbesar selalu berada pada posisi akar maka heap ini disebut max heap. Sebaliknya jika perbandingannya yaitu elemen terkecilnya selalu berada di simpul akar maka heap ini disebut min heap. perhatikan gambar dibawah.

Proses yang terjadi pada struktur data heap :

• Reorganisasi (Restrukturisasi) Heap
• Pembentukan Heap
• Penyisipan Heap
• Penghapusan Heap
• Pengurutan Data pada Heap (Heap Sort)

Reorganisasi heap 

Reorganisasi heap terjadi ketika terjadi perubahan terhadap heap, misalnya ketika penyisipan, penghapusan, pengupdatean dan pengurutan data.

Proses yang terjadi dalam reorganisasi heap adalah :

A. Shift-up (Geser ke atas)

Shift-Up adalah proses dimana sebuah nilai node bertambah sehingga nilai prioritasnya lebih besar dari parentnya.

Algoritmanya :
Tukarkan nilai node tersebut dengan nilai parent-nya.

Ulangi langkah a, sampai ditemukan posisi yang tepat (memenuhi kondisi heap)

B. Shift-down (Geser ke bawah)

Shift-Down adalah proses dimana sebuah nilai node berkurang sehingga nilainya lebih kecil dari anak-anaknya.

Algoritmanya :

Tukarkan nilai simpul yang berubah dengan nilai dari child yang mempunyai prioritas terbesar.

Ulangi langkah a, sampai ditemukan posisi yang tepat (memenuhi kondisi heap)

Pembentukan Heap

jika suatu complete binary tree memiliki nilai secara acak, maka langkah yang harus dilakukan agar binary tree tersebut dapat disebut sebagai heap adalah dengan melakukan proses shift-down dari node tengah (banyaknode/2 atau N/2), menurun sampai node pertama.

Contoh kasus

Sebelum

Sesudah

Proses shift-down dari simpul bernomor tengah (banyak simpul/2 atau N/2), menurun sampai simpul pertama. N = 6, Tengah = N/2 = 6/2 = 3, Lakukan reorganisasi pada simpul ke-2, Lakukan reorganisasi pada simpul ke-1. Perhatikan animasi gift berikut agar lebih jelas.

Penyisipan Data

Algoritma penyisipan data dalam Heap :

Simpan elemen baru tersebut setelah data paling akhir (tree dengan level paling bawah dan pada posisi sebelah kanan dari data terakhir atau jika level telah penuh, maka simpan data baru tersebut dalam level baru).

Lakukan reorganisasi heap pada node baru tersebut. Proses yang biasanya dipakai adalah proses shift-up. Banyak simpul ditambah 1

Penghapusan Data

Algoritma penghapusan heap  :

Ambil Nilai Heap pada node terakhir, dan dipakai sebagai nilai root. Lakukan proses reorganisasi heap pada root. Umumnya proses yang dilakukan adalah proses sift down. Banyak simpul dikurang 1

Pengurutan Data Heap

Algoritmanya :

N : banyakdata. tukarkan node root dengan node paling akhir (tempatkan nilai paling besar di akhir,

Kurangi nilai N dengan 1 (untuk menjaga nilai paling besar tidak usah dilibatkan lagi). lakukan reorganisasi heap dari node tengah sampai node 1. lakukan langkah b sampai d sampai N=0

Contoh Soal

Urutkan data pada tabel di bawah ini secara descending berdasarkan Nama, menggunakan metode Heap Sort.

Pembentukan CBT

Pembentukan Heap

Pengurutan Heap

Hasil pengurutan bedasarkan metode heap sort maka hasil nya akan seperti berikut.

Sebelum di urutkan

Sesudah diurutkan