Skip to content Skip to sidebar Skip to footer

Pengertian dan contoh soal pada struktur data heap tree

Pengertian dan contoh soal pada heap struktur data


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.

Pengertian dan contoh soal pada heap struktur data

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.

Pengertian dan contoh soal pada heap struktur data

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)

Pengertian dan contoh soal pada heap struktur data


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)

Pengertian dan contoh soal pada heap struktur data

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
Pengertian dan contoh soal pada heap struktur data

Sesudah

Pengertian dan contoh soal pada heap struktur data

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.

Pengertian dan contoh soal pada heap struktur data



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

Pengertian dan contoh soal pada heap struktur data

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

Pengertian dan contoh soal pada heap struktur data

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

Pengertian dan contoh soal pada heap struktur data

Contoh Soal

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

Pengertian dan contoh soal pada heap struktur data

Pembentukan CBT

Pengertian dan contoh soal pada heap struktur data

Pembentukan Heap

Pengertian dan contoh soal pada heap struktur data


Pengurutan Heap

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

Pengertian dan contoh soal pada heap struktur data
Sebelum di urutkan


Pengertian dan contoh soal pada heap struktur data
Sesudah diurutkan





Post a Comment for "Pengertian dan contoh soal pada struktur data heap tree"

Berlangganan via Email