การเรียงลำดับฮีปแบ่งออกเป็นสองกระบวนการ:
1. สร้างกอง
ฮีปเป็นต้นไม้ไบนารีที่สมบูรณ์และต้องเป็นไปตามต่อไปนี้: คำหลักของโหนดที่ไม่ใช่ใบใด ๆ ในต้นไม้ไม่เกิน (หรือไม่น้อยกว่า) คำหลักของเด็ก (ถ้ามี) โหนด
กองแบ่งออกเป็น: กองรากขนาดใหญ่และกองรากขนาดเล็ก คำสั่งซื้อจากน้อยไปมากใช้ในการเรียงลำดับกองรากขนาดใหญ่และคำสั่งจากมากไปน้อยใช้ในการเรียงลำดับรูรากขนาดเล็ก
หากเป็นฮีปรูทขนาดใหญ่โหนดที่มีค่าที่ใหญ่ที่สุดจะถูกปรับให้เป็นรูทฮีปโดยการปรับฟังก์ชั่น
2. บันทึกฮีปรูทที่หางและเรียกใช้ฟังก์ชันการปรับสำหรับลำดับที่เหลือ หลังจากการปรับเสร็จสมบูรณ์ให้บันทึกผู้ติดตามสูงสุดที่หาง -1 (-1, -2, ... , -i) จากนั้นปรับลำดับที่เหลือและทำซ้ำกระบวนการจนกว่าการเรียงลำดับจะเสร็จสมบูรณ์
การคัดลอกรหัสมีดังนี้:
// ปรับฟังก์ชั่น
ฟังก์ชั่น headadjust (องค์ประกอบ, pos, len) {
// บันทึกค่าโหนดปัจจุบัน
var swap = องค์ประกอบ [pos];
// ค้นหาโหนดลูกทางด้านซ้ายของโหนดปัจจุบัน
var child = pos * 2 + 1;
// เรียกซ้ำจนกว่าจะไม่มีลูก
ในขณะที่ (เด็ก <len) {
// หากโหนดปัจจุบันมีโหนดลูกทางด้านขวาและโหนดลูกที่เหมาะสมมีขนาดใหญ่กว่าให้ใช้โหนดลูกที่เหมาะสม
// เปรียบเทียบกับโหนดปัจจุบัน
ถ้า (เด็ก + 1 <len && องค์ประกอบ [เด็ก] <องค์ประกอบ [เด็ก + 1]) {
เด็ก += 1;
-
// เปรียบเทียบโหนดปัจจุบันกับโหนดลูกที่ใหญ่ที่สุดหากค่าน้อยกว่าให้ทำการแลกเปลี่ยนมูลค่าและค้นหาโหนดปัจจุบันหลังจากการแลกเปลี่ยน
// บนโหนดลูก
ถ้า (องค์ประกอบ [pos] <องค์ประกอบ [เด็ก]) {
องค์ประกอบ [pos] = องค์ประกอบ [เด็ก];
pos = เด็ก;
เด็ก = pos * 2 + 1;
-
อื่น{
หยุดพัก;
-
องค์ประกอบ [pos] = swap;
-
-
// สร้างกอง
ฟังก์ชั่น buildheap (องค์ประกอบ) {
// เริ่มจากโหนดสุดท้ายกับโหนดลูกเปรียบเทียบโหนดกับโหนดลูก
// หลังจากแลกเปลี่ยนตัวเลขที่ใหญ่ที่สุดด้วยโหนดนี้กระบวนการแลกเปลี่ยนเดียวกันจะดำเนินการกับโหนดด้านหน้าในทางกลับกัน
// จนกว่าจะมีการสร้างฮีปด้านบนขนาดใหญ่ (คำสั่งซื้อจากน้อยไปมากมีขนาดใหญ่คำสั่งลดลงจะมีขนาดเล็ก)
สำหรับ (var i = elements.length/2; i> = 0; i-) {
headadjust (องค์ประกอบ, i, elements.length);
-
-
การจัดเรียงฟังก์ชั่น (องค์ประกอบ) {
// สร้างกอง
BuildHeap (องค์ประกอบ);
// ปรับจากส่วนท้ายของลำดับ
สำหรับ (var i = elements.length-1; i> 0; i-) {
// ด้านบนของกองเป็นองค์ประกอบที่ใหญ่ที่สุดเสมอดังนั้นด้านบนของกองและองค์ประกอบหางจะถูกแลกเปลี่ยน
// องค์ประกอบสูงสุดจะถูกบันทึกไว้ในตอนท้ายและไม่ได้เข้าร่วมในการปรับครั้งต่อไป
var swap = องค์ประกอบ [i];
องค์ประกอบ [i] = องค์ประกอบ [0];
องค์ประกอบ [0] = แลกเปลี่ยน;
// ทำการปรับเปลี่ยนองค์ประกอบสูงสุดที่ด้านบนของกอง
Headadjust (องค์ประกอบ, 0, i);
-
-
องค์ประกอบ var = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];
console.log ('ก่อน:' + องค์ประกอบ);
เรียงลำดับ (องค์ประกอบ);
console.log ('หลังจาก:' + องค์ประกอบ);
ประสิทธิภาพ:
ความซับซ้อนของเวลา: ดีที่สุด: o (nlog2n), แย่ที่สุด: o (nlog2n), เฉลี่ย: o (nlog2n)
ความซับซ้อนของพื้นที่: O (1)
เสถียรภาพ: ไม่เสถียร