ในการเรียนรู้การเรียงลำดับกองคุณต้องเข้าใจแนวคิดของกอง มันสามารถประมาณเป็นวิธีการจัดเก็บอาร์เรย์เป็นต้นไม้ไบนารีอย่างสมบูรณ์ แต่มีคุณสมบัติอื่น ๆ กับเขาซึ่งคล้ายกับต้นไม้เรียงลำดับไบนารี มีความแตกต่างระหว่างกองที่ใหญ่ที่สุดและกองที่เล็กที่สุด ของโหนดลูก การเรียงลำดับฮีปโดยทั่วไปใช้กองที่ใหญ่ที่สุดในขณะที่กองที่เล็กที่สุดสามารถสร้างคิวลำดับความสำคัญ มีวิธีการในกองที่ใช้ในการรักษาคุณสมบัติของฮีปซึ่งเป็นวิธี MaxHeap ในรหัสของเราด้านล่าง อาร์เรย์และพารามิเตอร์ที่สองคือการปรับฮีป องค์ประกอบที่ถูกต้องเก็บไว้ในกองจริง บางทีความยาวของอาร์เรย์คือจำนวนองค์ประกอบที่เก็บไว้ในกองจริง ๆ แต่ไม่จำเป็นต้องเป็นข้อมูลทั้งหมดที่เราต้องสร้างกองสูงสุด การแนะนำอัลกอริทึมบอกว่าโหนดย่อยด้านซ้ายคือ 2xi แต่อาร์เรย์ของเรานับจาก 0 ดังนั้นโหนดย่อยด้านซ้ายจะกลายเป็น 2xi+1 2 คือโหนดลูกของจุดเหล่านี้คือโหนดใบไม้ทั้งหมดดังนั้นเราจึงสร้างกองสูงสุดโดยการเรียงลำดับจากล่างขึ้นบน ตรวจสอบให้แน่ใจว่าโหนดทั้งหมดในกองของเราตรงกับคุณสมบัติกองสูงสุด ในที่สุดการเรียงลำดับฮีปคือการเอาโหนดแรกเรียงลำดับโหนดที่เหลืออีกครั้งจากนั้นนำโหนดรูทออก สิ่งนี้ทำให้มั่นใจได้ว่าทุกครั้งที่เรานำมันออกมามันเป็นค่าสูงสุด
การคัดลอกรหัสมีดังนี้:
ชั้นเรียนสาธารณะ heapsort {
private int getleft (int i) {
กลับ 2*i+1;
-
ส่วนตัว int getright (int i) {
กลับ 2*i+2;
-
โมฆะสาธารณะ MaxHeap (int [] heap, int loc, ขนาด int) {
int l = getLeft (loc);
int r = getright (loc);
int ที่ใหญ่ที่สุด = loc;
if (l <size && heap [l]> heap [loc]) {
ใหญ่ที่สุด = l;
-
if (r <size && heap [r]> heap [ใหญ่ที่สุด]) {
ใหญ่ที่สุด = r;
-
ถ้า (ใหญ่ที่สุด! = loc) {
int cache = heap [loc];
heap [loc] = heap [ใหญ่ที่สุด];
กอง [ใหญ่ที่สุด] = แคช;
MaxHeap (กองขนาดใหญ่ขนาด);
-
-
โมฆะสาธารณะ buildHeap (int [] heap) {
สำหรับ (int i = heap.length/2; i> = 0; i-) {
MaxHeap (heap, i, heap.length);
-
-
การจัดเรียงโมฆะสาธารณะ (int [] heap) {
buildheap (heap);
สำหรับ (int i = heap.length-1; i> 1; i-) {
int cache = heap [0];
heap [0] = heap [i];
heap [i] = แคช;
MaxHeap (heap, 0, i);
-
int cache = heap [0];
heap [0] = heap [1];
กอง [1] = แคช;
-
โมฆะคงที่สาธารณะหลัก (สตริง [] args) {
int [] heap = new int [] {4,1,5,3,7,12,65,7};
heapsort hs = heapsort ใหม่ ();
hs.sort (heap);
สำหรับ (int i = 0; i <heap.length; i ++) {
System.out.println (heap [i]);
-
-
-