การเรียงลำดับของกอง: การใช้กองรากขนาดใหญ่
อาร์เรย์ทั้งหมดจะถูกป้อนลงในกองจากนั้นกองจะถูกปล่อยออกมาจากกองและแทรกกลับเข้าไปในอาร์เรย์จากด้านหน้าไปด้านหน้าและอาร์เรย์จะได้รับคำสั่งจากขนาดเล็กถึงใหญ่
Public Class MaxHeap <T ขยายการเปรียบเทียบ <? super t >> {ข้อมูลส่วนตัว t []; ขนาด int ส่วนตัว; กำลังการผลิต INT ส่วนตัว Public MaxHeap (ความจุ int) {this.data = (t []) ใหม่เปรียบเทียบ [ความจุ + 1]; ขนาด = 0; this.capacity = ความจุ; } ขนาด int สาธารณะ () {return this.size; } บูลีนสาธารณะ isempty () {ขนาดคืน == 0; } public int getCapacity () {return this.capacity; } / ** * @return ดูรากสูงสุด (ดูโดยไม่ต้องลบเมื่อเทียบกับ popmax) * / สาธารณะ t seekmax () {ส่งคืนข้อมูล [1]; } การแลกเปลี่ยนโมฆะสาธารณะ (int i, int j) {ถ้า (i! = j) {t temp = data [i]; ข้อมูล [i] = data [j]; ข้อมูล [j] = อุณหภูมิ; }} การแทรกโมฆะสาธารณะ (รายการ t) {size ++; ข้อมูล [ขนาด] = รายการ; shiftup (ขนาด); } / ** * @return ป๊อปรูทสูงสุด (ป๊อปอัพหมายถึงการลบเมื่อเทียบกับ seekmax) * / สาธารณะ t popmax () {swap (1, ขนาด-); Shiftdown (1); ส่งคืนข้อมูล [ขนาด + 1]; } / ** * @param child เครื่องหมายมุมล่างของโหนดเด็กคือเด็กและตารางมุมล่างของโหนดแม่คือลูก / 2 * / โมฆะสาธารณะ shiftup (เด็ก int) {ในขณะที่ (เด็ก> 1 && data [เด็ก]. compareto (ข้อมูล [เด็ก / 2])> 0) {swap เด็ก = เด็ก / 2; }}/*** @param เครื่องหมายมุมล่างขององค์ประกอบในอาร์เรย์ข้อมูล* @param b เครื่องหมายมุมล่างขององค์ประกอบในอาร์เรย์ข้อมูล* @กลับมาเครื่องหมายมุมล่างขององค์ประกอบที่มีขนาดใหญ่*/int ส่วนตัวสูงสุด (int a, int b) {ถ้า (data [a] ข้อมูล [a] big return a; // return a}}/*** @param เครื่องหมายมุมล่างขององค์ประกอบในอาร์เรย์ข้อมูล* @param b เครื่องหมายมุมล่างขององค์ประกอบในอาร์เรย์ข้อมูล* @param c ใหญ่ที่สุด = สูงสุด (ใหญ่ที่สุด, c); กลับมาใหญ่ขึ้น }/** * @param พ่อเครื่องหมายมุมล่างของโหนดพ่อแม่เป็นพ่อและโต๊ะมุมล่างทางซ้ายและขวาโหนดเด็กสองโหนดคือ: พ่อ * 2 และพ่อ * 2 + 1 */โมฆะสาธารณะ Shiftdown (int พ่อ) {ในขณะที่ (จริง) {int lchild = พ่อ * 2; ใครคือเครื่องหมายมุมล่างของผู้ปกครองโหนดซ้ายและขวา? ถ้า (lchild> ขนาด) {// ถ้าโหนดพ่อไม่มีลูกซ้ายหรือลูกกลับมา } อื่นถ้า (rchild> ขนาด) {// ถ้าโหนดพ่อมีลูกเหลือเพียงเด็กที่ถูกต้องนิวเคลียส = สูงสุด (พ่อ, lchild); } else {// ถ้าโหนดพ่อมีทั้งลูกซ้ายและลูกใหม่ Newfather = สูงสุด (พ่อ, lchild, rchild); } ถ้า (newfather == พ่อ) {// หมายความว่าพ่อมีขนาดใหญ่กว่าโหนดเด็กทั้งสองและชื่อตารางเป็นกองรากขนาดใหญ่อยู่แล้วดังนั้นจึงไม่จำเป็นต้องปรับการส่งคืนต่อไป } else {// มิฉะนั้นคุณจะต้องดำเนินการต่อเพื่อปรับกองจนกว่าจะมีการตอบสนองของกองรากขนาดใหญ่ (พ่อ, Newfather); // พ่อแลกเปลี่ยนค่า = newfather; // อัพเดทค่าของพ่อซึ่งเทียบเท่ากับการปรับเปลี่ยน shiftdown super t >> void sort (t [] arr) {int len = arr.length; // in-heap maxHeap <t> maxHeap = new MaxHeap <T> (len); สำหรับ (int i = 0; i <len; i ++) {maxheap.insert (arr [i]); } // out-heap สำหรับ (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 (); } โมฆะคงที่สาธารณะหลัก (สตริง args []) {จำนวนเต็ม [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printarr (arr); // 3 5 1 7 2 9 8 0 4 6 เรียงลำดับ (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}การเรียงลำดับของฮีป: สร้างกองบนอาร์เรย์ (กองสูงสุด)
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); สำหรับ (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 (); } โมฆะคงที่สาธารณะหลัก (สตริง args []) {จำนวนเต็ม [] arr = {3, 5, 1, 7, 2, 9, 8, 0, 4, 6}; printarr (arr); // 3 5 1 7 2 9 8 0 4 6 เรียงลำดับ (arr); printarr (arr); // 0 1 2 3 4 5 6 7 8 9}}ตัวอย่างการเรียงลำดับฮีปด้านบน (การใช้งานอาร์เรย์ Java) เป็นเนื้อหาทั้งหมดที่ฉันแบ่งปันกับคุณ ฉันหวังว่าคุณจะให้ข้อมูลอ้างอิงและฉันหวังว่าคุณจะสนับสนุน wulin.com มากขึ้น