Isih Timbunan Dalam Jawa

Heapsort di Java ialah teknik pengisihan berasaskan perbandingan, di mana struktur data Binary Heap digunakan. Isihan ini hampir sama dengan isihan pemilihan, di mana elemen terbesar akan dipilih, dan tempat pada akhirnya, dan proses itu akan diulang untuk semua elemen. Untuk memahami Isih Timbunan, mari kita lihat Isihan Timbunan Binari dalam Java.

• Struktur Data berasaskan pokok.
• Pokok Binari Lengkap.
• Ia boleh mempunyai sehingga dua orang anak.
• Nilai dalam nod akar boleh lebih besar (Timbunan Maks) atau Lebih Kecil (Timbunan Min)

Bagaimana Heap Sort berfungsi dalam Java?

Sebelum beralih ke algoritma, mari kita lihat apa itu Heapify.

IKLAN Kursus Popular dalam kategori ini JAVA MASTERY - Pengkhususan | 78 Siri Kursus | 15 Ujian Olok-olok

Heapify

Selepas timbunan dibuat dengan data input, sifat timbunan mungkin tidak berpuas hati. Untuk mencapainya, fungsi yang dipanggil heapify akan digunakan untuk melaraskan nod timbunan. Jika kita ingin mencipta timbunan maks, elemen semasa akan dibandingkan dengan anak-anaknya, dan jika nilai kanak-kanak lebih besar daripada elemen semasa, pertukaran akan dilakukan dengan elemen terbesar dalam anak kiri atau kanan. Begitu juga, jika timbunan min perlu dibuat, pertukaran akan dilakukan dengan elemen terkecil dalam anak kiri atau kanan. Sebagai Contoh, Berikut ialah tatasusunan input kami,

Kita boleh menganggap ini sebagai pokok dan bukannya Array. Elemen pertama akan menjadi akar; yang kedua akan menjadi anak kiri akar; elemen ketiga akan menjadi anak kanan akar, dan seterusnya.

Untuk mengubah timbunan menjadi pokok, rentas pokok itu ke arah bawah ke atas. Memandangkan nod daun tidak mempunyai anak, mari kita lihat ke peringkat seterusnya. iaitu 5 dan 7.

Kita boleh bermula pada pukul 5 kerana ia berada di sebelah kiri. Di sini, 5 mempunyai dua anak: 9 dan 4, di mana 9 lebih besar daripada nod induk 5. Untuk menjadikan ibu bapa lebih besar, kami akan menukar 5 dan 9. Selepas bertukar, pokok akan menjadi seperti yang ditunjukkan di bawah.

Mari kita beralih ke elemen seterusnya, 7, di mana 8 dan 2 adalah kanak-kanak. Serupa dengan elemen 9 dan 4, 7 dan 8 akan ditukar seperti dalam pokok di bawah.

Akhirnya, 3 mempunyai dua anak-9 dan 8, di mana 9 lebih besar dalam kalangan kanak-kanak dan akar. Jadi, pertukaran 3 dan 9 akan dilakukan untuk menjadikan akar lebih besar. Ulangi proses sehingga timbunan yang sah terbentuk, seperti ditunjukkan di bawah.

Algoritma untuk Isih Timbunan dalam Tertib Menaik

1. Buat Timbunan Maks dengan data input
2. Ganti elemen terakhir dengan elemen terbesar dalam timbunan
3. Timbunkan Pokok
4. Ulang proses sehingga tatasusunan diisih

Algoritma untuk Isih Timbunan dalam Susunan Menurun

1. Buat Timbunan Min dengan data input
2. Ganti elemen terakhir dengan elemen terkecil dalam timbunan
3. Timbunkan Pokok
4. Ulang proses sehingga tatasusunan diisih

Sekarang, mari kita cuba mengisih Timbunan yang diperoleh di atas dalam tertib menaik menggunakan algoritma yang diberikan. Pertama, keluarkan elemen terbesar. iaitu root dan gantikan dengan elemen terakhir.

Sekarang, timbunkan pokok yang terbentuk dan masukkan elemen yang dialih keluar dalam tatasusunan terakhir, seperti yang ditunjukkan di bawah.

Sekali lagi, keluarkan elemen akar, gantikan dengan elemen terakhir dan Timbunkannya.

Masukkan elemen yang dikeluarkan ke kedudukan kosong. Kini anda dapat melihat bahawa penghujung tatasusunan sedang diisih.

Sekarang, Alih keluar elemen 7 dan gantikan dengan 2.

Timbunkan pokok, seperti ditunjukkan di bawah.

Ulang proses sehingga tatasusunan diisih. Mengalih keluar elemen 5.

Timbunkan pokok.

Mengalih keluar elemen 4.

Bertambah lagi. 

Akhirnya, tatasusunan yang diisih seperti ini akan terbentuk.

Contoh

Sekarang, mari kita lihat kod sumber Heap Sort dalam Java

//Java program to sort the elements using Heap sort
import java.util.Arrays;
public class HeapSort {
public void sort(int array[]) {
int size = array.length; //Assigning the length of array in a variable
// Create heap
for (int i = size / 2 - 1; i >= 0; i--)
heapify(array, size, i);
//Find the maximum element and replace it with the last element in the array
for (int i=size-1; i>=0; i--) {
int x = array[0];//largest element(It is available in the root)
array[0] = array[i];
array[i] = x;
// Recursively call <u>heapify</u> until a heap is formed
heapify(array, i, 0);
}
}
// <u>Heapify</u> function
void heapify(int array[], int SizeofHeap, int i) {
int largestelement = i; // Set largest element as root
int leftChild  = 2*i + 1; // index of left child = 2*i + 1
int rightChild  = 2*i + 2; //index of right child  = 2*i + 2
// left child is greater than root
if (leftChild  < SizeofHeap && array[leftChild ] > array[largestelement])
largestelement = leftChild ;
//right child is greater than largest
if (rightChild  < SizeofHeap && array[rightChild ] > array[largestelement])
largestelement = rightChild ;
// If <u>largestelement</u> is not root
if (largestelement != i) {
int temp = array[i];
array[i] = array[largestelement];
array[largestelement] = temp;
// Recursive call to  heapify the sub-tree
heapify(array, SizeofHeap, largestelement);
}
}
public static void main(String args[]) {
int array[] = {3,5,7,9,4,8,2};
System.<em>out</em>.println("Input array is: " + Arrays.<em>toString</em>(array));
HeapSort obj = new HeapSort();
obj.sort(array);
System.<em>out</em>.println("Sorted array is : " + Arrays.<em>toString</em>(array));
}
}

Output

Kesimpulan

Isih Timbunan ialah teknik isihan yang bergantung pada struktur Data Timbunan Binari. Ia hampir serupa dengan isihan pemilihan dan tidak menggunakan tatasusunan berasingan untuk mengisih dan timbunan.

 Artikel Disyorkan

Ini telah menjadi panduan untuk Heap Sort di Java. Di sini kita membincangkan kerja, Algoritma Pengisihan dengan Susunan Menaik dan Menurun dan contoh dengan kod sampel. Anda juga boleh menelusuri artikel cadangan kami yang lain untuk mengetahui lebih lanjut –

1. Gabung Isih Dalam Java
2. Isih Timbunan dalam C
3. Isih Timbunan dalam C++
4. Isih Pemilihan dalam Struktur Data

Atas ialah kandungan terperinci Isih Timbunan Dalam Jawa. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!