Pahami Bagaimana Menerapkan Binary Heap di Java

Artikel ini akan memberi Anda gambaran umum lengkap tentang cara kerja heap sort dan nanti kita akan belajar mengimplementasikan Binary Heap di Java.

Berikut agenda artikel ini:

1. Apa itu jenis heap?
2. Max Heap
3. Min Heap
4. Implementasi Heap di Java
   • Diagram
   • Kode

Mari kita mulai!

Apa itu jenis heap?

Heap pada dasarnya adalah struktur data berbasis pohon. Ini memiliki node. Node terdiri dari elemen tertentu. Setiap node mengandung satu elemen.

Node mungkin memiliki anak. Jika seandainya tidak ada anak, itu disebut Daun.

Ada dua aturan yang harus diikuti:

• Nilai setiap node harus kurang atau sama dengan semua nilai yang disimpan pada turunannya.
• Ini memiliki ketinggian yang paling mungkin.

Heaps sangat efisien dalam mengekstraksi fileelemen terkecil atau terbesar.

Mari beralih ke tumpukan minimal sekarang!

cara keluar dari program di java

Min Heap

Min heap adalah pohon biner lengkap di mana nilai elemen root kurang dari atau sama dengan salah satu elemen turunan.

Representasi dari min heap

Tiba [(i-1) / 2]: ini akan mengembalikan simpul induk.

Ar [(2 * i) + 1]: ini akan mengembalikan simpul anak kiri.

Ar [(2 * i) + 2]: ini akan mengembalikan simpul anak yang benar.

Ada beberapa metode Min Heap:

• memasukkan(): Kunci baru di ujung pohon ditambahkan. Jika kunci baru lebih besar dari induknya, maka tidak perlu melakukan apa pun, jika tidak, kita harus melintasi untuk menyiapkan properti heap.
• getMin (): metode ini membantu mengembalikan elemen root.
• extractMin (): metode ini mengembalikan nilai minimumelemen.

Pindah ke tumpukan Max sekarang.

Heap maks

Heap maks adalah pohon biner lengkap di mana nilai elemen root lebih besar atau sama dengan salah satu elemen turunan.

Heap maks juga terdiri dari beberapa metode!

• Memasukkan (): itu akan memasukkan elemen di heap.
• Menghapus() : ini akan menghapus elemen dari heap.
• FindMax (): itu akan menemukan elemen maksimum dari heap.
• printHeap (): Ini akan mencetak konten heap

Sekarang izinkan saya menunjukkan kepada Anda implementasi heap melalui diagram dan kemudian Javakode.

Implementasi Heap di Java

Diagram:

cara menggunakan namespace di c ++

Diagram di atas menunjukkan heap biner di Java. Seperti yang telah Anda pelajari bahwa ada dua heap: Min heap dan Max heap, berikut adalah diagramnya:

Sekarang, beralih ke segmen berikutnya, kita akan melihat bagaimana mengimplementasikan tumpukan biner di Java.

Kode:

public class BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * Ini akan menginisialisasi heap dengan ukuran default. * / public BinaryHeap (int capacity) {heapSize = 0 heap = new int [capacity + 1] Arrays.fill (heap, -1)} / ** * Ini akan memeriksa apakah heap kosong atau tidak * Complexity: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * Ini akan memeriksa apakah heap sudah penuh atau tidak * Complexity: O (1) * / public boolean isFull () {return heapSize == heap .length} private int parent (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * Ini akan memasukkan elemen baru ke heap * Kompleksitas: O (log N) * Sebagai skenario kasus terburuk, kita perlu melintasi sampai root * / public void insert (int x) {if (isFull ()) membuang NoSuchElementException baru ('Heap is full, No space to insert elemen baru ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * Ini akan menghapus elemen pada indeks x * Kompleksitas: O (log N) * * / public int delete (int x) {if (isEmpty ()) melempar NoSuchElementException baru ('Heap is empty, No element to delete') int key = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn key} / ** * Metode ini digunakan untuk mempertahankan properti heap sambil menyisipkan elemen. * * / private void heapifyUp (int i) {int temp = heap [i] while (i> 0 && temp> heap [parent (i)]) {heap [i] = heap [parent (i)] i = parent (i)} heap [i] = temp} / ** * Metode ini digunakan untuk mempertahankan properti heap saat menghapus elemen. * * / private void heapifyDown (int i) {int child int temp = heap [i] while (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * Metode ini digunakan untuk mencetak semua elemen dari heap * * / public void printHeap () {System.out.print ('nHeap =') for (int i = 0 i
Dengan ini, kita sampai pada akhir artikel tentang Binary Heap di Java ini. Lihat    oleh Edureka, perusahaan pembelajaran online tepercaya dengan jaringan lebih dari 250.000 pelajar yang puas dan tersebar di seluruh dunia. Kursus pelatihan dan sertifikasi Java J2EE dan SOA Edureka dirancang untuk siswa dan profesional yang ingin menjadi Pengembang Java. Kursus ini dirancang untuk memberi Anda permulaan dalam pemrograman Java dan melatih Anda untuk konsep Java inti dan lanjutan bersama dengan berbagai kerangka kerja Java seperti Hibernate & Spring. 
 Ada pertanyaan untuk kami? Harap sebutkan di bagian komentar di blog 'Java ArrayList' ini dan kami akan menghubungi Anda kembali secepatnya.