Struktur Data Heap: Apa itu Heap? Tumpukan Min & Maks (Contoh)

Apa itu Tumpukan?

Heap adalah struktur data pohon yang terspesialisasi. Heap terdiri dari simpul paling atas yang disebut akar (induk). Anak keduanya adalah anak kiri akar, sedangkan simpul ketiga adalah anak kanan akar. Simpul-simpul berikutnya diisi dari kiri ke kanan. Kunci simpul induk dibandingkan dengan kunci keturunannya, dan terjadilah susunan yang tepat. Pohon mudah divisualisasikan di mana setiap entitas disebut simpul. Simpul memiliki kunci unik untuk identifikasi.

Mengapa Anda memerlukan Struktur Data Heap?

Berikut adalah alasan utama menggunakan Struktur Data Heap:

Struktur data heap memungkinkan penghapusan dan penyisipan dalam waktu logaritmik – O(log₂N).
Data di pohon dibentuk dalam urutan tertentu. Selain memperbarui atau menanyakan hal-hal seperti maksimum atau minimum, pemrogram dapat menemukan hubungan antara induk dan keturunannya.
Anda bisa menerapkan konsep tersebut Model Objek Dokumen untuk membantu Anda memahami struktur data heap.

Jenis Tumpukan

Struktur data heap memiliki berbagai algoritma untuk menangani penyisipan dan penghapusan elemen dalam struktur data heap, termasuk Priority-Queue, Binary-Heap, Binomial Heap, dan Sortir Tumpukan.

Antrian Prioritas: Ini adalah struktur data abstrak yang berisi objek yang diprioritaskan. Setiap objek atau item mempunyai prioritas yang telah diatur sebelumnya. Oleh karena itu, objek atau item yang diberi prioritas lebih tinggi akan mendapatkan layanan sebelum yang lain.
Tumpukan Biner: Tumpukan biner cocok untuk operasi tumpukan sederhana seperti penghapusan dan penyisipan.
Binomial-Heap: Tumpukan binomial terdiri dari serangkaian kumpulan pohon binomial yang membentuk tumpukan tersebut. Pohon Tumpukan Binomial bukanlah pohon biasa karena didefinisikan secara ketat. Jumlah elemen dalam pohon binomial selalu memiliki 2ⁿ node.
Sortir Tumpukan: Tidak seperti kebanyakan algoritma pengurutan, heap-sort menggunakan ruang O(1) untuk operasi pengurutannya. Ini adalah algoritma pengurutan berbasis perbandingan di mana pengurutan terjadi dalam urutan menaik dengan terlebih dahulu mengubahnya menjadi heap maksimum. Anda dapat melihat Heapsort sebagai pohon pencarian biner dengan kualitas yang ditingkatkan.

Biasanya, struktur data heap menggunakan dua strategi. Untuk masukan 12 – 8 – 4 – 2 dan 1

Min Heap – nilai terkecil di atas
Max Heap – nilai tertinggi di bagian atas

tumpukan minimum

Dalam struktur Min Heap, node akar memiliki nilai yang sama atau lebih kecil dari nilai anak pada node tersebut. Node heap dari Min Heap ini memiliki nilai minimum. Secara keseluruhan, struktur min-heap-nya sudah lengkap pohon biner.

Setelah Anda memiliki tumpukan Min di pohon, semua daun merupakan kandidat yang layak. Namun, Anda perlu memeriksa setiap daun untuk mendapatkan nilai Max-heap yang tepat.

Contoh Tumpukan Min

Pada diagram di atas, Anda dapat melihat beberapa urutan yang jelas dari akar hingga simpul terbawah.

Misalkan Anda menyimpan elemen-elemen di Array Array_N[12,2,8,1,4]. Seperti yang dapat Anda lihat dari array, elemen akar melanggar prioritas Min Heap. Untuk mempertahankan properti Min heap, Anda harus melakukan operasi min-heapify untuk menukar elemen-elemen hingga properti Min heap terpenuhi.

Tumpukan Maks

Dalam struktur Max Heap, node induk atau root memiliki nilai yang sama atau lebih besar dari anaknya di node tersebut. Node ini memegang nilai maksimum. Selain itu, ini adalah pohon biner lengkap, sehingga Anda dapat membuat tumpukan maksimal dari kumpulan nilai dan menjalankannya dalam waktu O(n).

Berikut adalah beberapa metode untuk mengimplementasikan java max heap

Menambahkan (): menempatkan elemen baru ke dalam heap. Jika Anda menggunakan array, objek ditambahkan di akhir array, sedangkan di pohon biner, objek ditambahkan dari atas ke bawah dan kemudian dari kiri ke kanan.
Menghapus (): Metode ini memungkinkan Anda menghapus elemen pertama dari daftar array. Karena elemen yang baru ditambahkan bukan lagi yang terbesar, metode Sift-Down selalu mendorongnya ke lokasi barunya.
Ayak-Bawah (): Metode ini membandingkan objek akar dengan anaknya, lalu mendorong simpul yang baru ditambahkan ke posisi yang seharusnya.
Penyaringan (): jika Anda menggunakan metode array untuk menambahkan elemen yang baru disisipkan ke dalam array, maka metode Sift-Up membantu node yang baru ditambahkan tersebut berpindah ke posisi barunya. Item yang baru disisipkan pertama kali dibandingkan dengan induknya dengan mensimulasikan struktur data pohon.
Terapkan rumus Parent_Index=Child_Index/2. Anda terus melakukan ini hingga elemen maksimum berada di depan array.

Tumpukan Dasar Operations

Agar Anda dapat menemukan nilai tertinggi dan terendah dalam sekumpulan data, Anda memerlukan banyak operasi heap dasar seperti menemukan, menghapus, dan menyisipkan. Karena elemen akan terus-menerus datang dan pergi, Anda harus:

Menemukan – Cari item di tumpukan.
Menyisipkan – Tambahkan anak baru ke heap.
Delete – Menghapus node dari heap.

Buat Tumpukan

Proses membangun tumpukan dikenal sebagai pembuatan tumpukan. Dengan daftar kunci, pemrogram membuat tumpukan kosong lalu memasukkan kunci lain satu per satu menggunakan operasi tumpukan dasar.

Jadi mari kita mulai membuat Min-heap menggunakan metode Willaim dengan memasukkan nilai 12,2,8,1 dan 4 ke dalam heap. Anda dapat membangun heap dengan n elemen dengan memulai dengan heap kosong dan kemudian mengisinya secara berurutan dengan elemen lain menggunakan waktu O (nlogn).

Heapify: dalam algoritma penyisipan, yang membantu menyisipkan elemen ke dalam tumpukan. Pemeriksaan, apakah struktur data tumpukan properti disorot, diikuti.
Misalnya, heapify maks akan memeriksa apakah nilai induk lebih besar daripada keturunannya. Elemen-elemen tersebut kemudian dapat diurutkan menggunakan metode seperti swapping.

Gabung: Mengingat Anda memiliki dua heap untuk digabungkan menjadi satu, gunakan merge heaps untuk menyatukan nilai dari dua heap. Namun, tumpukan aslinya masih dipertahankan.

Periksa Tumpukan

Memeriksa Heaps mengacu pada pemeriksaan jumlah elemen dalam struktur data heap dan memvalidasi apakah heap kosong.

Penting untuk memeriksa tumpukan sebagai penyortiran atau pengantrean elemen. Memeriksa apakah Anda memiliki elemen untuk diproses menggunakan Is-Empty() adalah penting. Ukuran tumpukan akan membantu menemukan tumpukan maksimum atau tumpukan minimum. Jadi, Anda perlu mengetahui elemen yang mengikuti properti tumpukan.

Ukuran – mengembalikan besaran atau panjang heap. Anda dapat mengetahui berapa banyak elemen yang diurutkan.
Kosong – jika heap bernilai NULL, maka akan mengembalikan TRUE, jika tidak maka akan mengembalikan FALSE.

Di sini, Anda mencetak semua elemen di prioritasQ loop dan kemudian memeriksa apakah prioritasQ tidak kosong.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

Penggunaan Struktur Data Heap

Struktur data heap berguna dalam banyak aplikasi pemrograman dalam kehidupan nyata seperti:

Membantu dalam Penyaringan Spam.
Menerapkan algoritma grafik.
Operating Penyeimbangan beban sistem, dan kompresi data.
Temukan urutannya dalam statistik.
Terapkan antrean Prioritas tempat Anda dapat mencari item dalam daftar dalam waktu logaritmik.
Struktur data tumpukan juga digunakan untuk penyortiran.
Mensimulasikan pelanggan secara online.
Penanganan interupsi di OperaSistem ting.
Dalam pengkodean Huffman untuk kompresi data.

Properti Antrean Prioritas Heap

Dalam tumpukan prioritas, item data dalam daftar dibandingkan satu sama lain untuk menentukan elemen yang lebih kecil.
Sebuah elemen ditempatkan dalam antrian dan kemudian dihapus.
Setiap elemen dalam Antrean Prioritas memiliki nomor unik terkait yang diidentifikasi sebagai prioritas.
Setelah keluar dari Antrean Prioritas, elemen prioritas utama keluar terlebih dahulu.

Langkah-langkah mengimplementasikan heap Priority Queue in Java

Sortir Tumpukan di JAVA dengan Contoh Kode

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap the root and the largest element and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

Keluaran

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

Sortir Tumpukan Python dengan Contoh Kode

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)