รหัส Java เป็นตัวอย่างอธิบายคุณสมบัติการดำเนินการขั้นพื้นฐานและวิธีการเรียงลำดับของ heaps

คุณสมบัติของกอง
กองเป็นต้นไม้ไบนารีที่สมบูรณ์ซึ่งสามารถนำไปใช้ในความเป็นจริงผ่านอาเรย์ หนึ่งในคุณสมบัติที่สำคัญที่สุดคือโหนดใด ๆ มีขนาดเล็กกว่า (มากกว่า) เท่ากับโหนดลูก กองที่มีโหนดรากที่เล็กที่สุดเรียกว่ากองที่เล็กที่สุดและกองที่มีโหนดรูทที่ใหญ่ที่สุดเรียกว่ากองที่ใหญ่ที่สุด รูปต่อไปนี้แสดงตัวอย่างของกองที่ใหญ่ที่สุดและการเป็นตัวแทนอาร์เรย์ซึ่งสามารถเห็นได้อย่างสังหรณ์ใจว่าแต่ละโหนดมีขนาดใหญ่กว่าเด็ก

ดังที่เห็นได้ในรูปด้านบนโหนดของทรีไบนารีอย่างสมบูรณ์สามารถจัดเรียงตามลำดับจากหมายเลขโหนดรูท 1 ซึ่งสอดคล้องกับดัชนีในอาร์เรย์ A (โปรดทราบว่าตัวห้อยที่นี่เริ่มต้นจาก 1) เมื่อได้รับโหนด I เราสามารถรับลูกซ้ายได้อย่างง่ายดายคือ 2i, เด็กที่ถูกต้องคือ 2i+1 และโหนดแม่คือ i/2

การดำเนินงานขั้นพื้นฐานของกอง
มีการดำเนินการพื้นฐานสองประการสำหรับกอง (ดูฮีปขั้นต่ำเป็นตัวอย่างด้านล่าง):
แทรกองค์ประกอบ k: เพิ่ม k โดยตรงไปยังส่วนท้ายของอาร์เรย์แล้วฟองขึ้นเพื่อปรับกอง การทำงานของ Bubble Up: เปรียบเทียบองค์ประกอบที่จะปรับให้เข้ากับโหนดพาเรนต์และถ้ามันมากกว่าโหนดพาเรนต์ให้แลกเปลี่ยนจนกว่าคุณสมบัติของกองจะถูกกู้คืน
แยกค่ามากที่สุด: ค่ามากที่สุดคือองค์ประกอบรูท จากนั้นลบออกให้องค์ประกอบรูท = องค์ประกอบโหนดใบสุดท้ายจากนั้นฟองลงจากองค์ประกอบรูทเพื่อปรับฮีป การทำงานของ Bubble Down: ในแต่ละครั้งคุณควรเลือกโหนดลูกที่เล็กที่สุดจากสามโหนดเพื่อปรับโหนดซึ่งมีเด็กซ้ายและขวาเพื่อแลกเปลี่ยน (ถ้าเล็กที่สุดไม่จำเป็นต้องแลกเปลี่ยนตัวเอง) จนกว่าคุณสมบัติของกองจะถูกกู้คืน
ในทางปฏิบัติมักจำเป็นต้องสร้างอาร์เรย์ที่ไม่มีการเรียงลำดับซึ่งมีองค์ประกอบ N เป็นกอง ตัวสร้างในคลาสฮีปด้านล่างจะแสดงวิธีการสร้างกองผ่านการปรับฟองสบู่ _bubbledown ลง กองเป็นต้นไม้ไบนารีที่สมบูรณ์และความสูงของต้นไม้จะถูกlognlog⁡nเสมอ การดำเนินการใช้เวลานานของการดำเนินการพื้นฐานแต่ละครั้งคือการเดือดปุด ๆ และปรับให้เข้ากับคุณสมบัติของกองดังนั้นความซับซ้อนของเวลาคือ o (nlogn) o (nlog⁡n)
ตัวอย่าง Java:

 // ลอยโมฆะสาธารณะว่ายน้ำ (int k) {ในขณะที่ (k/2> = 1 && น้อยลง (pq [k/2], pq [k])) {exch (pq, k/2, k); k = k/2; }} // sink private void sink () {int k = 1; ในขณะที่ (2*k <n) {int j = 2*k; ถ้า (น้อยกว่า (pq [j], pq [j+1])) j ++; ถ้า (น้อยกว่า (pq [k], pq [j])) แลกเปลี่ยน (pq, k, j); แตกอื่น; k = j; -

หลักการดำเนินการเรียงลำดับกอง
แบ่งออกเป็นสองขั้นตอน:
1. จัดเรียงอาร์เรย์ตามลำดับ Binary Heap
2. เปลี่ยนตำแหน่งของโหนดรูทและโหนดสุดท้ายจากนั้นจมลงในโหนดรูท

ทำให้สำเร็จ:
บางทีรหัสของฉันอาจแตกต่างจากภาพเคลื่อนไหวด้านบนเล็กน้อย แต่หลักการพื้นฐานนั้นคล้ายคลึงกัน

 Public Class Heapsort ขยายฐาน {private int n; @Override public void sort (เทียบเท่า [] a) {n = a.length-1; int k = n/2; ในขณะที่ (k> = 1) {sink (a, k); K--; } k = 1; ในขณะที่ (k <= n) {exch (a, k, n--); Sink (a, k); -