java max heap

3 min read 02-10-2024

Max heap adalah salah satu struktur data yang digunakan dalam algoritma pemrograman. Ini adalah jenis heap, di mana setiap node memiliki nilai yang lebih besar daripada anak-anaknya. Dalam artikel ini, kita akan menjelaskan bagaimana cara kerja max heap, cara mengimplementasikannya dalam Java, dan memberikan beberapa contoh penggunaan yang relevan.

Apa Itu Max Heap?

Max heap adalah struktur data berbasis pohon biner yang memenuhi dua syarat utama:

Heap Property: Setiap node memiliki nilai yang lebih besar atau sama dengan nilai anak-anaknya.
Complete Binary Tree: Max heap selalu berupa pohon biner lengkap, yang berarti setiap level penuh kecuali untuk level terakhir yang terisi dari kiri ke kanan.

Dengan struktur ini, elemen terbesar selalu berada di root. Ini menjadikan max heap sangat berguna dalam pengimplementasian algoritma pencarian maksimum, algoritma pengurutan (heap sort), dan bahkan dalam aplikasi pengelolaan prioritas (priority queue).

Contoh Kode Max Heap di Java

Berikut adalah contoh sederhana pengimplementasian max heap dalam Java:

class MaxHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MaxHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        heap = new int[capacity];
    }

    private int parent(int index) { return (index - 1) / 2; }
    private int leftChild(int index) { return 2 * index + 1; }
    private int rightChild(int index) { return 2 * index + 2; }

    private void swap(int index1, int index2) {
        int temp = heap[index1];
        heap[index1] = heap[index2];
        heap[index2] = temp;
    }

    public void insert(int value) {
        if (size == capacity) {
            throw new IllegalStateException("Heap is full");
        }
        heap[size] = value;
        size++;
        heapifyUp(size - 1);
    }

    private void heapifyUp(int index) {
        while (index != 0 && heap[parent(index)] < heap[index]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    public int extractMax() {
        if (size == 0) {
            throw new IllegalStateException("Heap is empty");
        }
        int max = heap[0];
        heap[0] = heap[size - 1];
        size--;
        heapifyDown(0);
        return max;
    }

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

        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest != index) {
            swap(index, largest);
            heapifyDown(largest);
        }
    }
}

Analisis Kode

Struktur Kelas: Kelas MaxHeap memiliki atribut seperti heap, size, dan capacity. heap adalah array untuk menyimpan elemen, size adalah jumlah elemen saat ini, dan capacity adalah batas maksimum elemen yang dapat disimpan.
Metode insert: Metode ini menambahkan elemen ke heap dan memanggil heapifyUp untuk memastikan properti heap tetap terjaga.
Metode extractMax: Menghapus elemen maksimum (root) dari heap, memindahkan elemen terakhir ke root, dan kemudian memanggil heapifyDown untuk menyusun kembali heap.

Contoh Penggunaan

Mari kita lihat bagaimana kita dapat menggunakan kelas MaxHeap:

public class Main {
    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(10);
        maxHeap.insert(3);
        maxHeap.insert(1);
        maxHeap.insert(14);
        maxHeap.insert(7);
        
        System.out.println("Max Value: " + maxHeap.extractMax()); // Output: 14
        System.out.println("Max Value: " + maxHeap.extractMax()); // Output: 7
    }
}

Output dari program ini menunjukkan bagaimana kita bisa mendapatkan elemen terbesar dari max heap setelah menambah beberapa nilai.

Kesimpulan

Max heap adalah struktur data yang sangat berguna dalam pemrograman, dan pemahaman tentang cara kerjanya bisa memberikan keuntungan dalam menyelesaikan berbagai masalah algoritmik. Dengan menggunakan Java, Anda bisa dengan mudah mengimplementasikan dan memanfaatkan max heap dalam berbagai aplikasi. Jika Anda tertarik untuk mengeksplorasi lebih lanjut, pertimbangkan untuk membaca sumber daya tambahan tentang algoritma pengurutan dan manajemen prioritas.

Sumber Daya Tambahan

Dengan artikel ini, Anda kini memiliki pemahaman yang lebih baik tentang max heap di Java. Selamat mencoba!