Tumpukan biner adalah tumpukan khusus. Tumpukan biner adalah pohon biner lengkap (pohon biner) atau pohon biner yang kira -kira lengkap (pohon biner). Ada dua jenis tumpukan biner: tumpukan terbesar dan tumpukan terkecil. Tumpukan Maksimum: Nilai kunci dari simpul induk selalu lebih besar dari atau sama dengan nilai kunci dari setiap node anak; Tumpukan Minimum: Nilai kunci dari simpul induk selalu kurang dari atau sama dengan nilai kunci dari setiap node anak.
Print Binary Heap: Memanfaatkan hubungan hierarkis
Di sini saya pertama -tama mengurutkan tumpukan, dan kemudian menjalankan metode untuk mencetak heap di sort printAsTree()
Kelas Publik MaxHeap <T memperluas yang sebanding <? super t >> {private t [] data; ukuran int pribadi; kapasitas int pribadi; public maxHeap (int kapasitas) {this.capacity = kapasitas; this.size = 0; this.data = (t []) baru sebanding [kapasitas + 1]; } public maxheap (t [] arr) {// heapify, array heap capasity = arr.length; data = (t []) baru sebanding [kapasitas + 1]; System.ArrayCopy (ARR, 0, Data, 1, arr.length); size = arr.length; untuk (int i = ukuran / 2; i> = 1; i--) {shiftown (i); }} public int size () {return this.size; } public int getCapacity () {return this.capacity; } public boolean isEmpty () {return size == 0; } public T seekMax () {return data [1]; } swap public void (int i, int j) {if (i! = j) {t temp = data [i]; data [i] = data [j]; data [j] = temp; }} public void insert (t item) {size ++; data [ukuran] = item; shiftup (ukuran); } public t popmax () {swap (1, size--); shiftdown (1); Mengembalikan data [ukuran + 1]; } public void shiftup (int child) {while (anak> 1 && data [anak] .compareto (data [anak / 2])> 0) {swap (anak, anak / 2); anak /= 2; }}/*** @param Tanda sudut bawah elemen dalam array data* @param b tanda sudut bawah elemen dalam array data* @return return elemen mana yang lebih besar, tanda sudut bawah dari elemen mana yang lebih besar*/int private int max (int a, int b) {if (a] .compareto (data [b] <0) {if {if (a]. data[a] big return a;//Return a } } /** * @param a lower corner mark of an element in the data array* @param b lower corner mark of an element in the data array* @param c The lower corner mark of an element in the data array* @return The lower corner mark of which element is larger*/ private int max(int a, int b, int c) { int biggest = max(a, b); terbesar = maks (terbesar, c); kembali terbesar; } public void shiftDown (int ayah) {while (true) {int lChild = ayah * 2; int rchild = ayah * 2 + 1; int newfather = ayah; // tidak masalah apakah penugasan ditetapkan di sini. Jika pengembalian berikut diubah menjadi pecah, itu harus ditetapkan jika (ukuran lchild>) {// Jika tidak ada anak kiri dan kanan kembali; } lain jika (rchild> size) {// jika tidak ada anak yang benar newFather = max (ayah, lchild); } else {// Jika ada anak -anak kiri dan kanan newFather = max (ayah, lchild, rchild); } if (newFather == ayah) {// Jika simpul induk asli adalah yang terbesar dari tiga, Anda tidak perlu terus memilah tiang punggung; } else {// simpul induk bukan yang terbesar, bertukar anak yang lebih tua dan terus menyesuaikan ke bawah sampai tumpukan akar yang besar dipenuhi pertukaran (NewFather, ayah); ayah = newfather; // setara dengan shiftdown (newfather). Jika Newfather ternyata adalah anak kiri ayah, itu setara dengan shiftdown (2*ayah)}}} public static <t meluas sebanding <? super t >> void sort (t [] arr) {int len = arr.length; Maxheap <t> maxheap = maxheap baru <> (arr); maxheap.printastree (); untuk (int i = len-1; i> = 0; i--) {arr [i] = maxheap.popmax (); }} public static void printarR (objek [] arr) {for (objek o: arr) {system.out.print (o); System.out.print ("/t"); } System.out.println (); } public void printspace (int n) {// print n spaces (digunakan dengan '/t' di sini sebagai gantinya) untuk (int i = 0; i <n; i ++) {System.out.printf ("%3s", ""); }} public void printAstree () {int linenum = 1; // Pertama melintasi baris int line pertama = (int) (math.log (size)/math.log (2)) + 1; // garis adalah jumlah lapisan spacenum int heap = (int) (math.pow (2, baris) - 1); untuk (int i = 1; i <= size;) {// Karena data disimpan di interval tertutup kiri dan kanan dalam [1 ... ukuran], data [0] tidak menyimpan data // setiap lapisan mencetak interval ini [2^(Nomor Layer-1) ... (Nomor Lapisan 2^) -1]. Jika angka dalam tumpukan tidak cukup (2^ lapisan) -1, cetak ke ukuran. Jadi ambil min ((2^ lapisan) -1, ukuran). untuk (int j = (int) math.pow (2, linenum - 1); j <= math.min (size, (int) math.pow (2, linenum) - 1); j ++) {printspace (spacenum); // Cetak ruang dengan spacenum system.out.printf ("%3s", data [j]); // cetak data data.out.printf ("%3s", ""); // kotak hijau di gambar printspace (spacenum); // Cetak ruang dengan Spacenum I ++; // Setiap elemen dicetak, itu+1} linenum ++; Spacenum = Spacenum / 2; System.out.println (); }} public static void main (string args []) {integer [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6, 1, 3, 6, 1, 1}; urutkan (arr); }}Hasil Eksekusi:
Meringkaskan
Di atas adalah semua konten artikel ini tentang berbagi kode pencetakan bahasa Java yang mengimplementasikan tumpukan biner. Saya harap ini akan membantu semua orang. Teman yang tertarik dapat terus merujuk ke topik terkait lainnya di situs ini. Jika ada kekurangan, silakan tinggalkan pesan untuk menunjukkannya. Terima kasih teman atas dukungan Anda untuk situs ini!