กองไบนารีเป็นกองพิเศษ กองไบนารีเป็นต้นไม้ไบนารีที่สมบูรณ์ (ต้นไม้ไบนารี) หรือต้นไม้ไบนารีที่สมบูรณ์ (ต้นไม้ไบนารี) กองไบนารีมีสองประเภท: กองที่ใหญ่ที่สุดและกองเล็กที่สุด ฮีปสูงสุด: ค่าคีย์ของโหนดพาเรนต์จะสูงกว่าหรือเท่ากับค่าคีย์ของโหนดลูกใด ๆ ฮีปขั้นต่ำ: ค่าคีย์ของโหนดพาเรนต์มักจะน้อยกว่าหรือเท่ากับค่าคีย์ของโหนดลูกใด ๆ
พิมพ์ฮีปไบนารี: ใช้ความสัมพันธ์แบบลำดับชั้น
ที่นี่ฉันเรียงลำดับกองก่อนแล้วจึงดำเนินการวิธีการพิมพ์ฮีปใน Sort printAsTree()
Public Class MaxHeap <T ขยายการเปรียบเทียบ <? super t >> {ข้อมูลส่วนตัว t []; ขนาด int ส่วนตัว; กำลังการผลิต INT ส่วนตัว Public MaxHeap (ความจุ int) {this.capacity = ความจุ; this.size = 0; this.data = (t []) ใหม่เปรียบเทียบ [ความจุ + 1]; } Public MaxHeap (T [] arr) {// heapify, array heap heap ความจุ = arr.length; data = (t []) ใหม่เปรียบเทียบ [ความจุ + 1]; System.ArrayCopy (arr, 0, ข้อมูล, 1, arr.length); ขนาด = arr.length; สำหรับ (int i = size / 2; i> = 1; i--) {shiftdown (i); }} ขนาด int สาธารณะ () {return this.size; } public int getCapacity () {return this.capacity; } บูลีนสาธารณะ isempty () {ขนาดคืน == 0; } สาธารณะ t seekmax () {ส่งคืนข้อมูล [1]; } การแลกเปลี่ยนโมฆะสาธารณะ (int i, int j) {ถ้า (i! = j) {t temp = data [i]; ข้อมูล [i] = data [j]; ข้อมูล [j] = อุณหภูมิ; }} การแทรกโมฆะสาธารณะ (รายการ t) {size ++; ข้อมูล [ขนาด] = รายการ; shiftup (ขนาด); } สาธารณะ t popmax () {swap (1, ขนาด-); Shiftdown (1); ส่งคืนข้อมูล [ขนาด + 1]; } โมฆะสาธารณะ shiftup (int child) {ในขณะที่ (เด็ก> 1 && data [child] .compareto (ข้อมูล [เด็ก / 2])> 0) {swap (เด็ก, เด็ก / 2); เด็ก /= 2; }}/*** @param เครื่องหมายมุมล่างขององค์ประกอบในอาร์เรย์ข้อมูล* @param b เครื่องหมายมุมล่างขององค์ประกอบในอาร์เรย์ข้อมูล* @return return องค์ประกอบที่มีขนาดใหญ่กว่าเครื่องหมายมุมล่างขององค์ประกอบที่ใหญ่กว่า*/ส่วนตัว int max (int a, int b) {ถ้าข้อมูล {// ถ้าข้อมูล [a] big return a; // return a}}/*** @param เครื่องหมายมุมล่างขององค์ประกอบในอาร์เรย์ข้อมูล* @param b เครื่องหมายมุมล่างขององค์ประกอบในอาร์เรย์ข้อมูล* @param c ใหญ่ที่สุด = สูงสุด (ใหญ่ที่สุด, c); กลับมาใหญ่ที่สุด; } โมฆะสาธารณะ shiftdown (int พ่อ) {ในขณะที่ (จริง) {int lchild = พ่อ * 2; int rchild = พ่อ * 2 + 1; int newfather = พ่อ; // ไม่สำคัญว่าการมอบหมายจะได้รับมอบหมายที่นี่หรือไม่ หากผลตอบแทนต่อไปนี้ถูกเปลี่ยนเป็นตัวแบ่งจะต้องได้รับการกำหนดถ้า (ขนาด lchild>) {// หากไม่มีลูกซ้ายและขวากลับมา; } อื่นถ้า (rchild> ขนาด) {// ถ้าไม่มีลูกใหม่ที่ถูกต้อง = สูงสุด (พ่อ, lchild); } else {// ถ้ามีเด็กซ้ายและขวา Newfather = สูงสุด (พ่อ, lchild, rchild); } ถ้า (newfather == พ่อ) {// ถ้าโหนดแม่ดั้งเดิมนั้นใหญ่ที่สุดในสามคุณไม่จำเป็นต้องจัดเรียงกองกลับ } else {// โหนดพาเรนต์ไม่ใหญ่ที่สุดสลับกับเด็กโตและปรับตัวลงเรื่อย ๆ จนกระทั่งกองรากขนาดใหญ่มีความพึงพอใจในการแลกเปลี่ยน (Newfather พ่อ); พ่อ = newfather; // เทียบเท่ากับ Shiftdown (Newfather) หาก Newfather กลายเป็นลูกซ้ายของพ่อมันจะเทียบเท่ากับ shiftdown (2*พ่อ)}}} สาธารณะคงที่ <t ขยายเปรียบเทียบได้ <? super t >> void sort (t [] arr) {int len = arr.length; MaxHeap <T> maxHeap = new MaxHeap <> (arr); MaxHeap.printastrere (); สำหรับ (int i = len-1; i> = 0; i--) {arr [i] = maxheap.popmax (); }} โมฆะคงที่สาธารณะ printarr (วัตถุ [] arr) {สำหรับ (วัตถุ o: arr) {system.out.print (o); System.out.print ("/t"); } system.out.println (); } โมฆะสาธารณะ printspace (int n) {// print n ช่องว่าง (ใช้กับ '/t' แทน) สำหรับ (int i = 0; i <n; i ++) {system.out.printf ("%3S", ""); }} public void printastree () {int linenum = 1; // traverse แรกบรรทัดบรรทัดแรก int บรรทัด = (int) (math.log (ขนาด)/math.log (2)) + 1; // บรรทัดคือจำนวนเลเยอร์ของ heap int spacenum = (int) (math.pow (2, บรรทัด) - 1); สำหรับ (int i = 1; i <= size;) {// เนื่องจากข้อมูลถูกเก็บไว้ในช่วงเวลาด้านซ้ายและขวาปิดใน [1 ... ขนาด], ข้อมูล [0] ไม่เก็บข้อมูล // แต่ละเลเยอร์พิมพ์ช่วงเวลานี้ [2^(เลเยอร์หมายเลข 1) ... (หมายเลขเลเยอร์ 2^) -1] หากหมายเลขในกองไม่เพียงพอ (2^ เลเยอร์) -1 ให้พิมพ์เป็นขนาด ดังนั้นใช้เวลาน้อย ((2^ เลเยอร์) -1, ขนาด) สำหรับ (int j = (int) math.pow (2, linenum - 1); j <= math.min (ขนาด, (int) math.pow (2, ผ้าลินิน) - 1); j ++) {printspace (spacenum); // พิมพ์ช่องว่างด้วย spacenum system.out.printf ("%3S", ข้อมูล [J]); // พิมพ์ data system.out.printf ("%3s", ""); // กล่องสีเขียวในภาพ printspace (spacenum); // พิมพ์ช่องว่างด้วย spacenum i ++; // ทุกองค์ประกอบถูกพิมพ์มันคือ+1} ผ้าลินิน ++; spacenum = spacenum / 2; System.out.println (); }} โมฆะคงที่สาธารณะหลัก (สตริง args []) {integer [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6, 1, 3, 6, 1, 1, 1}; เรียงลำดับ (arr); -ผลการดำเนินการ:
สรุป
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้เกี่ยวกับการแบ่งปันรหัสการพิมพ์ของภาษา Java ที่ใช้กองไบนารี ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคน เพื่อนที่สนใจสามารถอ้างถึงหัวข้ออื่น ๆ ที่เกี่ยวข้องในเว็บไซต์นี้ต่อไป หากมีข้อบกพร่องใด ๆ โปรดฝากข้อความไว้เพื่อชี้ให้เห็น ขอบคุณเพื่อนที่ให้การสนับสนุนเว็บไซต์นี้!