# Praktikum 1 ## 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` * Tambahkan juga konstruktor untuk kelas `Heap`. * Jangan lupa, import package yang dibutuhkan. {% code overflow="wrap" lineNumbers="true" %} ```java import java.util.ArrayList; import java.util.List; public class Heap { private List heap; public Heap() { this.heap = new ArrayList<>(); } ``` {% endcode %} * Tambahkan method `getHeap()` pada kelas `Heap`. {% code overflow="wrap" lineNumbers="true" %} ```java public List getHeap() { return new ArrayList<>(heap); } ``` {% endcode %} * 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$$. {% code overflow="wrap" lineNumbers="true" %} ```java private int leftChild(int index) { return 2 * index + 1; } ``` {% endcode %} * 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$$. {% code overflow="wrap" lineNumbers="true" %} ```java private int rightChild(int index) { return 2 * index + 2; } ``` {% endcode %} * Selanjutnya, untuk mengetahui index parent dari sebuah child, buatlah method bantuan dengan nama `parent(int index)`. {% code overflow="wrap" lineNumbers="true" %} ```java private int parent(int index) { return (index - 1) / 2; } ``` {% endcode %} * 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. {% code overflow="wrap" lineNumbers="true" %} ```java private void swap(int index1, int index2) { int temp = heap.get(index1); heap.set(index1, heap.get(index2)); heap.set(index2, temp); } ``` {% endcode %} * 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)`. {% code overflow="wrap" lineNumbers="true" %} ```java public void insert(int value) { // Menambahkan value ke dalam heap (dengan tipe List) 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); } } ``` {% endcode %} * 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. {% code overflow="wrap" lineNumbers="true" %} ```java 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); } } ``` {% endcode %} * Untuk menguji apakah heap yang dibuat dapat berjalan sesuai dengan kaidah heap, buatlah kelas `HeapMain` yang berisi main method untuk melakukan pengujian. {% code overflow="wrap" lineNumbers="true" %} ```java 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()); } } ``` {% endcode %} * 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? --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://polinema.gitbook.io/jti-modul-praktikum-algoritma-dan-struktur-data/struktur-data-non-linear/job-sheet-12-heap/praktikum-1.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.