ภาพรวม
การเรียงลำดับของฮีปเป็นการเรียงลำดับการเลือกต้นไม้ซึ่งเป็นการปรับปรุงที่มีประสิทธิภาพในการเรียงลำดับการเลือกโดยตรง
กองถูกกำหนดดังนี้: ลำดับขององค์ประกอบ n (k1, k2, ... , kn), ถ้าและเฉพาะในกรณีที่พอใจ:
มันถูกเรียกว่ากองในเวลานั้น ดังที่เห็นได้จากคำจำกัดความของฮีปองค์ประกอบด้านบนของฮีป (เช่นองค์ประกอบแรก) จะต้องเป็นรายการที่เล็กที่สุด (กองเล็ก ๆ ด้านบน) หรือรายการที่ใหญ่ที่สุด (กองบนขนาดใหญ่)
หากกองซ้อนถูกเก็บไว้ในอาร์เรย์หนึ่งมิติฮีปจะสอดคล้องกับต้นไม้ไบนารีที่สมบูรณ์และค่าของโหนดที่ไม่ใช่ใบทั้งหมด (โหนดที่มีเด็ก) จะไม่มากกว่า (หรือไม่น้อยกว่า) ค่าของเด็กและค่าของโหนดราก (องค์ประกอบด้านบนของกอง)
(a) ลำดับกองขนาดใหญ่: (96, 83, 27, 38, 11, 09)
(b) ลำดับกองเล็ก ๆ : (12, 36, 24, 85, 47, 30, 53, 91)
ในขั้นต้นลำดับของตัวเลข n ที่จะจัดเรียงถือเป็นต้นไม้ไบนารีที่เก็บไว้ตามลำดับ (การจัดเก็บอาร์เรย์หนึ่งมิติทรีไบนารีต้นไม้) ปรับลำดับการจัดเก็บของพวกเขาเพื่อให้เป็นกองส่งออกองค์ประกอบด้านบนของฮีปเพื่อให้ได้องค์ประกอบที่เล็กที่สุด (หรือใหญ่ที่สุด) ขององค์ประกอบ N จากนั้นปรับองค์ประกอบ N-1 ที่เหลือให้กลายเป็นฮีปส่งออกองค์ประกอบด้านบนของกองและรับองค์ประกอบที่เป็นขนาดเล็กที่สอง (หรือใหญ่ที่สอง) ในบรรดาองค์ประกอบ N และอื่น ๆ จนกว่าคุณจะได้รับลำดับที่สั่งซื้อด้วยโหนด n เรียกกระบวนการนี้เรียงลำดับ
ขั้นตอนและตัวอย่าง
มีสองปัญหาในการแก้ปัญหาการเรียงลำดับกอง:
(1) วิธีการสร้างตัวเลข n ที่จะจัดเรียงเป็นกอง;
(2) หลังจากเอาท์พุทองค์ประกอบด้านบนของกองวิธีปรับองค์ประกอบ N-1 ที่เหลือเพื่อให้เป็นกองใหม่
สร้างวิธีฮีป (กองเล็ก ๆ ด้านบน):
กระบวนการสร้างกองสำหรับลำดับเริ่มต้นเป็นกระบวนการของการคัดกรองซ้ำ
ต้นไม้ไบนารีที่สมบูรณ์ของโหนด n จากนั้นโหนดสุดท้ายคือทรีย่อยของโหนด n/2th
ตัวกรองเริ่มต้นด้วยทรีย่อยที่มีโหนด n/2 เป็นรูท (n/2 เป็นโหนดสุดท้ายที่มีทรีย่อย) เพื่อให้ทรีย่อยกลายเป็นฮีป
จากนั้นกรองทรีทรีสกับแต่ละโหนดเป็นรูทตามลำดับไปข้างหน้าเพื่อให้เป็นฮีปจนกระทั่งรูทโหนด
ดังที่แสดงในรูปลำดับที่ไม่เป็นระเบียบของกระบวนการเริ่มต้นของการสร้างกอง: (49, 38, 65, 97, 76, 13, 27, 49)
(a) ลำดับที่ไม่ได้เรียงลำดับทรีไบนารีเริ่มต้น 97 (8/2 = 4 โหนด) เป็นโหนดพาเรนต์ของโหนดสุดท้าย (49)
(b) 97> = 49 แทนที่ตำแหน่งจากนั้นกรองโหนดก่อนหน้า 65 ของ N/2
(c) 13 <= 27 และ 65> = 13 แทนที่ตำแหน่งของ 65 และ 13 จากนั้นแทนที่ 38 (ทั้งสองมากกว่านั้นไม่จำเป็นต้องมีการดำเนินการ), ตัวกรอง 49
(d) 13 <= 38 และ 49> = 13 แทนที่ตำแหน่งของ 49 และ 13, 49> = 27 แทนที่ตำแหน่งของ 49 และ 27
(e) ในที่สุดก็ได้รับกอง 13 คือหมายเลขขั้นต่ำที่เราได้รับ
วิธีการปรับกอง (กองด้านบนขนาดเล็ก):
มีการจัดเตรียมองค์ประกอบ M หลังจากเอาท์พุทองค์ประกอบด้านบนของกององค์ประกอบ M-1 จะถูกทิ้งไว้ องค์ประกอบด้านล่างของกองถูกป้อนไปที่ด้านบนของกองและกองถูกทำลายเนื่องจากโหนดรากไม่ตรงกับคุณสมบัติของกอง
แลกเปลี่ยนโหนดรูทด้วยองค์ประกอบที่เล็กกว่าในทรีย่อยด้านซ้ายและขวา
หากแลกเปลี่ยนกับทรีย่อยด้านซ้าย: หากกองทรีทรีซ้ายเสียหายวิธีทำซ้ำ (2)
หากแลกเปลี่ยนกับทรีย่อยที่ถูกต้องให้ทำซ้ำวิธี (2) หากกองทรีย่อยที่ถูกต้องถูกทำลาย
ดำเนินการดำเนินการแลกเปลี่ยนข้างต้นบนทรีทรีที่ไม่ตรงกับคุณสมบัติของฮีปจนกว่าจะมีการสร้างโหนดใบและกอง
ในการปรับกองคุณจะต้องพิจารณาโหนดที่เสียหายและโหนดอื่น ๆ ไม่จำเป็นต้องปรับ
การใช้งานรหัส (Java)
เรียกใช้รหัสและเปรียบเทียบความคิดเห็นกับขั้นตอนตัวอย่างข้างต้นสำหรับการเปรียบเทียบ
แพ็คเกจ com.coder4j.main; Public Class Heapsort { / ** * ปรับเป็นกองเล็ก ๆ ด้านบน (ผลลัพธ์มาจากขนาดใหญ่ถึงขนาดเล็กหลังจากการเรียงลำดับ) * * @param อาร์เรย์คืออาร์เรย์ที่จะปรับ * @param s เป็นตำแหน่งของอาร์เรย์ที่จะปรับความยาว * @param int tmp = อาร์เรย์ [s]; int child = 2 * s + 1; // ตำแหน่งของโหนดลูกซ้าย system.out.println ("โหนดที่จะปรับคือ: อาร์เรย์ [" + s + "] =" + tmp); ในขณะที่ (เด็ก <ความยาว) {// เด็ก + 1 เป็นเด็กที่เหมาะสมในขณะนี้การปรับโหนด // หากมีลูกที่เหมาะสมและมีขนาดเล็กกว่าเด็กซ้ายให้ใช้ลูกที่เหมาะสมเพื่อเปรียบเทียบกับโหนดมิฉะนั้นใช้เด็กซ้ายถ้า (เด็ก + 1 <ความยาว && อาร์เรย์ [ลูก]> อาร์เรย์ } system.out.println ("จะอยู่กับอาร์เรย์ลูก [" + เด็ก + "] =" + อาร์เรย์ [เด็ก] + "เปรียบเทียบ"); // ถ้าเด็กตัวเล็กมีขนาดเล็กกว่าโหนดนี้ถ้า (อาร์เรย์ [s]> อาร์เรย์ [เด็ก]) {system.out.println ("เด็กมีขนาดเล็กกว่าตำแหน่งการแลกเปลี่ยน"); อาร์เรย์ [s] = อาร์เรย์ [เด็ก]; // เลื่อนเด็กเล็กขึ้นไปและแทนที่โหนดปัจจุบันที่จะปรับ s = child; // ย้ายโหนดที่ปรับไปยังตำแหน่งเดิมของอาร์เรย์เด็กอายุน้อยกว่า [เด็ก] = TMP; child = 2 * s + 1; // ดำเนินการต่อเพื่อตัดสินว่าโหนดที่จะปรับจะต้องปรับต่อไปหรือไม่หาก (เด็ก> = ความยาว) {system.out.println ("ไม่มีเด็กการปรับจะจบ"); } else {system.out.println ("ดำเนินการต่อเพื่อเปรียบเทียบกับเด็กใหม่"); } // ดำเนินการต่อ; } else {system.out.println ("เด็กมีอายุมากกว่าพวกเขาการปรับจะจบลง"); break; // โหนดปัจจุบันที่จะปรับมีขนาดเล็กกว่าเด็กซ้ายและขวาและไม่จำเป็นต้องปรับออกออกไปโดยตรง}}}/ ** * ปรับเป็นกองบนขนาดใหญ่ (ผลลัพธ์จากขนาดเล็กไปยังใหญ่ heapadjustb (int [] อาร์เรย์, int s, ความยาว int) {int tmp = array [s]; int child = 2 * s + 1; // ตำแหน่งของโหนดลูกซ้าย system.out.println ("โหนดที่จะปรับคือ: อาร์เรย์ [" + s + "] =" + tmp); ในขณะที่ (เด็ก <ความยาว) {// เด็ก + 1 เป็นเด็กที่เหมาะสมในขณะนี้การปรับโหนด // หากมีลูกที่เหมาะสมและมีขนาดใหญ่กว่าเด็กซ้ายให้ใช้เด็กที่เหมาะสมเพื่อเปรียบเทียบกับโหนดมิฉะนั้นใช้เด็กซ้ายถ้า (เด็ก + 1 <ความยาว && อาร์เรย์ [เด็ก] <อาเรย์ } system.out.println ("จะอยู่กับอาร์เรย์ลูก [" + เด็ก + "] =" + อาร์เรย์ [เด็ก] + "เปรียบเทียบ"); // ถ้าเด็กโตมีขนาดใหญ่กว่าโหนดนี้ถ้า (อาร์เรย์ [s] <อาเรย์ [ลูก]) {system.out.println ("เด็กมีขนาดใหญ่กว่าตำแหน่งสลับ"); อาร์เรย์ [s] = อาร์เรย์ [เด็ก]; // ย้ายเด็กโตขึ้นไปด้านบนและแทนที่โหนดปัจจุบันที่จะปรับ s = child; // ย้ายโหนดที่ปรับไปยังตำแหน่งเดิมของอาร์เรย์เด็กโต [เด็ก] = TMP; child = 2 * s + 1; // ดำเนินการต่อเพื่อตัดสินว่าโหนดที่จะปรับจะต้องปรับหรือไม่ถ้า (child> = ความยาว) {system.out.println ("ไม่มีเด็กการปรับจะจบ"); } else {system.out.println ("ดำเนินการต่อเพื่อเปรียบเทียบกับเด็กใหม่"); } // ดำเนินการต่อ; } else {system.out.println ("เด็กมีขนาดเล็กกว่าพวกเขาการปรับจะจบลง"); break; // โหนดปัจจุบันที่จะปรับมีขนาดใหญ่กว่าเด็กซ้ายและขวาและออกโดยตรงโดยไม่ต้องปรับ}}}/ ** * อัลกอริทึมการเรียงลำดับฮีป * * @param array * @param ผกผันจริงตามลำดับที่ผิดพลาด 1) / 2 เพื่อปรับแต่ละโหนดขึ้นไปเพื่อให้สอดคล้องกับ HEAP System.out.println ("เริ่มต้นฮีปเริ่มต้น"); สำหรับ (int i = (array.length-1) / 2; i> = 0; i--) {ถ้า (ผกผัน) {heapadjusts (อาร์เรย์, i, array.length); } else {heapadjustb (อาร์เรย์, i, array.length); }} system.out.println ("เริ่มต้น heap end"); สำหรับ (int i = array.length-1; i> 0; i--) {// สลับองค์ประกอบของฮีปด้านบน h [0] และองค์ประกอบสุดท้ายในฮีป int tmp = อาร์เรย์ [i]; อาร์เรย์ [i] = อาร์เรย์ [0]; อาร์เรย์ [0] = TMP; // หลังจากสลับแต่ละองค์ประกอบฮีปด้านบนและองค์ประกอบสุดท้ายในกองจะต้องปรับฮีปถ้า (ผกผัน) {heapadjusts (อาร์เรย์, 0, i); } else {heapadjustb (อาร์เรย์, 0, i); }}} โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int [] array = {49, 38, 65, 97, 76, 13, 27, 49}; heapsort (อาร์เรย์, เท็จ); สำหรับ (int i: array) {system.out.print (i + ""); -ผลการทำงาน:
โหนดที่จะปรับที่จุดเริ่มต้นของกองเริ่มต้นคือ: อาร์เรย์ [3] = 97 เด็กจะเล็กลงด้วยอาร์เรย์เด็ก [7] = 49 เด็กมีขนาดเล็กกว่ากับเด็กและโหนดที่จะปรับในตอนท้ายของการปรับคือ: เด็กกำลังปรับตัวเล็ก ๆ อาร์เรย์ [1] = 38 เด็กมีขนาดใหญ่ขึ้นเมื่อเด็กอาเรย์ [3] = 49 เด็กมีขนาดใหญ่ขึ้นเมื่อเด็กอาเรย์ [0] = 49 เด็กมีขนาดเล็กกว่าด้วยอาเรย์เด็ก [2] = 13 เด็กมีขนาดเล็กกว่ากับเด็กอาเรย์ [6] = 27 เด็กมีขนาดเล็กกว่าตำแหน่งแลกเปลี่ยนและไม่มีลูกในการแลกเปลี่ยน โหนดที่จะปรับหลังจากการปรับคือ: อาร์เรย์ [0] = 97 เด็กมีขนาดเล็กกว่าเด็ก เด็กเล็กกว่าเด็ก ตำแหน่งการแลกเปลี่ยนยังคงเปรียบเทียบกับเด็กใหม่ เด็กคืออาร์เรย์ [6] = 49 เด็กมีขนาดเล็กกว่าตำแหน่งการแลกเปลี่ยนและไม่มีเด็กอยู่ในตำแหน่งการแลกเปลี่ยน โหนดที่จะปรับหลังจากการปรับคือ: อาร์เรย์ [0] = 97 เด็กมีขนาดเล็กกว่าเด็ก เด็กเล็กกว่าเด็ก เด็กเล็กกว่าเด็ก เด็กคืออาร์เรย์ [1] = 38 เด็กมีขนาดเล็กกว่าเด็ก เด็กคืออาร์เรย์ [3] = 49 เด็กมีขนาดเล็กกว่าเด็ก เด็กมีขนาดเล็กกว่าตำแหน่งการแลกเปลี่ยน โหนดที่จะปรับหลังจากการปรับคือ: อาร์เรย์ [0] = 65 เด็กคืออาร์เรย์ [1] = 49 เด็กมีขนาดเล็กกว่าเด็กและตำแหน่งการแลกเปลี่ยนยังคงเปรียบเทียบกับเด็กใหม่ เด็กจะใหญ่กว่าเด็ก โหนดที่จะปรับหลังจากการปรับคือ: อาร์เรย์ [0] = 76 เด็กมีขนาดใหญ่กว่าเด็ก โหนดที่จะปรับหลังจากการปรับคือ: อาร์เรย์ [0] = 76 เด็กมีขนาดเล็กกว่าเด็ก โหนดที่จะปรับหลังจากการปรับคือ: อาร์เรย์ [0] = 49 เด็กมีขนาดเล็กกว่าเด็ก โหนดที่จะปรับหลังจากการปรับคือ: อาร์เรย์ [0] = 97 เด็กมีขนาดเล็กกว่าเด็ก โหนดที่จะปรับหลังจากการปรับคือ: อาร์เรย์ [0] = 97 76 65 49 49 38 27 13
PS: ความแตกต่างระหว่างการเรียงลำดับฮีปและการเรียงลำดับโดยตรง
ในลำดับการเลือกโดยตรงเพื่อเลือกบันทึกด้วยคำหลักที่เล็กที่สุดจาก R [1..N] ต้องทำการเปรียบเทียบ N-1 จากนั้นเลือกบันทึกด้วยคำหลักที่เล็กที่สุดใน R [2..N] การเปรียบเทียบ N-2 จะต้องดำเนินการ ในความเป็นจริงในการเปรียบเทียบ N-2 ต่อไปนี้การเปรียบเทียบจำนวนมากอาจเกิดขึ้นในการเปรียบเทียบ N-1 ก่อนหน้า แต่เนื่องจากผลการเปรียบเทียบเหล่านี้ไม่ได้ถูกเก็บไว้ในลำดับก่อนหน้านี้การดำเนินการเปรียบเทียบเหล่านี้ซ้ำในระหว่างลำดับถัดไป
การเรียงลำดับฮีปสามารถบันทึกส่วนหนึ่งของผลการเปรียบเทียบผ่านโครงสร้างต้นไม้ซึ่งสามารถลดจำนวนการเปรียบเทียบ