🌿Praktikum 1

Implementasi Heap dengan ArrayList

Deskripsi

Pada praktikum ini, Anda akan membuat struktur data heap untuk kasus maximum prioritu queuing. Sehingga, tree akan disusun mulai dari yang terbesar. Selain itu, struktur heap yang akan Anda buat akan diterapkan dengan menggunakan ArrayList.

Langkah Praktikum

• Buatkan kelas Heap

• Tambahkan atribut heap dengan tipe List<Integer>

• Tambahkan juga konstruktor untuk kelas Heap.

• Jangan lupa, import package yang dibutuhkan.

import java.util.ArrayList;
import java.util.List;

public class Heap {
    private List<Integer> heap;

    public Heap() {
        this.heap = new ArrayList<>();
    }

• Tambahkan method getHeap() pada kelas Heap.

public List<Integer> getHeap() {
    return new ArrayList<>(heap);
}

• Selanjutnya, untuk melakukan pencekan terhahdap child sebelah kiri, buat method leftChild(int index) . Pada kasus ini, kita akan berasumsi bahwa index heap dimulai dari 0. sehingga nilai child kiri adalah $L_{index} = 2*i+1$.

private int leftChild(int index) {
    return 2 * index + 1;
}

• Tambakan pula method untuk pengecekan child sebelah kanan. Dikarenakan index heap dimulai dari 0, maka nilai index child sebelah kanan adalah $R_{index} = 2 * i + 2$.

private int rightChild(int index) {
    return 2 * index + 2;
}

• Selanjutnya, untuk mengetahui index parent dari sebuah child, buatlah method bantuan dengan nama parent(int index).

private int parent(int index) {
    return (index - 1) / 2;
}

• Pada heap, diperlukan proses menukar nilai ketika nilai pada susunan heap tidak valid. Oleh karena buat, buatlah method swap(int index1, int index2) yang akan digunakan untuk proses swap.

private void swap(int index1, int index2) {
    int temp = heap.get(index1);
    heap.set(index1, heap.get(index2));
    heap.set(index2, temp);
}

• Sampai pada tahap ini, Anda telah mengimplementasikan fungsi-fungsi dasar pada struktur data heap. Fungsi-fungsi tersebut nantinya akan digunakan pada proses penambahan dan pengurangan data.

• Untuk menambahkan data, buatlah method insert(int value).

public void insert(int value) {
    // Menambahkan value ke dalam heap (dengan tipe List<Integer>)
    heap.add(value);
    
    // Simpan index value yang baru saja ditambahkan
    int current = heap.size() - 1;
    
    // Lakukan swap selama value yang baru saja ditambahkan lebih besar dari parentnya
    while (current > 0 && heap.get(current) > heap.get(parent(current))) {
        swap(current, parent(current));
        current = parent(current);
    }
}

• Selanjutnya, untuk mengurani nilai pada heap, buatlah method remove(). Pada kasus ini, Anda membuat maximum priority queuing, sehingga, hanya node root yang akan dikeluarkan terlebih dahulu.

public Integer remove(){
    // Cek ketika kondisi heap kosong
    if(heap.size() == 0) {
        return null;
    }

    // Cek ketika kondisi heap berisi 1 data
    if (heap.size() == 1) {
        return heap.remove(0);
    }

    // Simpan index nilai terbesar (root)
    int maxValue = heap.get(0);
    
    // Proses swap
    heap.set(0, heap.remove(heap.size() - 1));
    sinkDown(0);

    return maxValue;
}

• Setelah proses penghapusan, heap harus menyusun kembali struktur data yang ada didalamnya agar tetap valid dengan mempertahankan struktur complete tree. Tambakan method sinkDown(int index) untuk menerapakan solusi dari kondisi tersebut.

private void sinkDown(int index) {
    int left = leftChild(index);
    int right = rightChild(index);
    int largest = index;

    // Ambil large kiri
    if (left < heap.size() && heap.get(left) > heap.get(largest)) {
        largest = left;
    }

    // Ambil large kanan
    if (right < heap.size() && heap.get(right) > heap.get(largest)) {
        largest = right;
    }

    // Proses penyesuaian nilai pada heap
    if (largest != index) {
        swap(index, largest);
        sinkDown(largest);
    }
}

• Untuk menguji apakah heap yang dibuat dapat berjalan sesuai dengan kaidah heap, buatlah kelas HeapMain yang berisi main method untuk melakukan pengujian.

public class HeapMain {
    public static void main(String[] args) {
        Heap heap = new Heap();

        heap.insert(95);
        heap.insert(75);
        heap.insert(80);
        heap.insert(55);
        heap.insert(60);
        heap.insert(50);
        heap.insert(65);

        System.out.println(heap.getHeap());

        heap.remove();

        System.out.println(heap.getHeap());

        heap.remove();

        System.out.println(heap.getHeap());
    }
}

• Jalankan program dan validasi hasilnya.

// Ekspektasi Hasil

[95, 75, 80, 55, 60, 50, 65]
[80, 75, 65, 55, 60, 50]
[75, 60, 65, 55, 50]

Pertanyaan

• Pada method swap terdapat method set yang dipanggil oleh objek heap. Apa fungsi dari set?

• Pada method remove digunakan nilai kembalian (return value) yaitu Integer. Apa perbedaan nilai kembalian antara Interger dan int? Mengapa digunakan Integer?

• Perhatikan method sinkDown baris ke-17 sampai ke-20. Proses apa yang dijalankan pada baris tersebut?