1. ฉันต้องพูดถึงต้นไม้ไบนารี
เพื่อให้เข้าใจกองคุณต้องเข้าใจต้นไม้ไบนารีก่อน ในวิทยาการคอมพิวเตอร์ต้นไม้ไบนารีเป็นโครงสร้างต้นไม้ที่มีทรีย่อยสองตัวต่อโหนดมากที่สุด โดยปกติแล้วทรีย่อยจะเรียกว่า "ทรีย่อยซ้าย" และ "ทรีย่อยขวา" ต้นไม้ไบนารีมักใช้เพื่อใช้ต้นไม้ค้นหาไบนารีและกองไบนารี
แต่ละโหนดของต้นไม้ไบนารีมีสองทรีย่อย (โหนดที่มีองศามากกว่า 2) ทรีทรีของต้นไม้ไบนารีสามารถแบ่งออกเป็นซ้ายและขวาและคำสั่งไม่สามารถย้อนกลับได้ ชั้น i -th ของต้นไม้ไบนารีมีมากที่สุด 2i - 1 โหนด; ต้นไม้ไบนารีที่มีความลึกของ K มีมากที่สุด 2K - 1 โหนด; สำหรับต้นไม้ไบนารีใด ๆ t หากจำนวนของโหนดเทอร์มินัลคือ N0 และจำนวนโหนดที่มีระดับ 2 คือ N2, N0 = N2 + 1
มีความแตกต่างหลักสามประการระหว่างต้นไม้และต้นไม้ไบนารี:
จำนวนโหนดในต้นไม้อย่างน้อย 1 ในขณะที่จำนวนโหนดในต้นไม้ไบนารีสามารถเป็น 0
ไม่มีขีด จำกัด ในระดับสูงสุดของโหนดในต้นไม้ในขณะที่ระดับสูงสุดของโหนดในต้นไม้ไบนารีคือ 2
ไม่มีความแตกต่างระหว่างซ้ายและขวาในโหนดของต้นไม้ในขณะที่ไม่มีความแตกต่างระหว่างซ้ายและขวาในโหนดของต้นไม้ไบนารี
ต้นไม้ไบนารีแบ่งออกเป็นต้นไม้ไบนารีที่สมบูรณ์และต้นไม้ไบนารีเต็มรูปแบบ
ต้นไม้ไบนารีเต็ม: ต้นไม้ที่มีความลึกของ K และมี 2K - 1 โหนดเรียกว่าต้นไม้ไบนารีเต็มรูปแบบ
(ต้นไม้ไบนารีเต็มความลึก 3)
ต้นไม้ไบนารีที่สมบูรณ์: ต้นไม้ไบนารีที่มีโหนด n ที่มีความลึก k มันถูกเรียกว่าต้นไม้ไบนารีที่สมบูรณ์หากและเฉพาะในกรณีที่แต่ละโหนดสอดคล้องกับโหนดที่มีหมายเลขลำดับ 1 ถึง N ในต้นไม้ไบนารีเต็มรูปแบบที่มีความลึก K
(ต้นไม้ไบนารีเต็มความลึก 3)
2. กองคืออะไร?
กอง (กองไบนารี) ถือได้ว่าเป็นต้นไม้ไบนารีที่สมบูรณ์ คุณสมบัติ "ยอดเยี่ยม" ของต้นไม้ไบนารีที่สมบูรณ์คือยกเว้นเลเยอร์ด้านล่างแต่ละชั้นจะเต็มซึ่งอนุญาตให้กองจะแสดงโดยอาร์เรย์ (ต้นไม้ไบนารีทั่วไปทั่วไปมักจะแสดงโดยรายการที่เชื่อมโยงเป็นคอนเทนเนอร์พื้นฐาน) และแต่ละโหนดสอดคล้องกับองค์ประกอบในอาร์เรย์
รูปต่อไปนี้แสดงความสัมพันธ์ระหว่างกองและอาร์เรย์
(ความสัมพันธ์ระหว่างกองและอาร์เรย์)
สำหรับ Subscript I ที่กำหนดของโหนดสามารถคำนวณได้ง่ายสำหรับตัวห้อยของโหนดพาเรนต์และโหนดลูกของโหนดนี้:
ผู้ปกครอง (i) = ชั้น (i/2) ตัวห้อยโหนดหลักของ i
ซ้าย (i) = 2i ตัวห้อยโหนดลูกซ้ายของ i
ถูกต้อง (i) = 2i + 1 ซึ่งเป็นตัวแยกโหนดลูกที่ถูกต้องของ i
โดยทั่วไปจะมีกองไบนารีสองประเภท: กองที่ใหญ่ที่สุดและกองที่เล็กที่สุด
กองสูงสุด:
ค่าองค์ประกอบสูงสุดในกองสูงสุดจะปรากฏที่โหนดรูท (ด้านบนของฮีป)
ค่าองค์ประกอบของแต่ละโหนดพาเรนต์ในกองมีค่ามากกว่าหรือเท่ากับโหนดลูก (ถ้ามีอยู่)
(กองสูงสุด)
กองขั้นต่ำ:
ค่าองค์ประกอบขั้นต่ำในกองขั้นต่ำจะปรากฏที่โหนดรูท (ด้านบนของฮีป)
ค่าองค์ประกอบของแต่ละโหนดพาเรนต์ในกองน้อยกว่าหรือเท่ากับโหนดลูก (ถ้ามีอยู่)
(สแต็คขั้นต่ำ)
3. หลักการของการเรียงลำดับกอง
การเรียงลำดับฮีปคือการนำจำนวนสูงสุดที่ด้านบนของกองสูงสุดให้ดำเนินการต่อเพื่อปรับกองที่เหลือให้เป็นกองสูงสุดและนำจำนวนสูงสุดที่ด้านบนของกองอีกครั้ง กระบวนการนี้จะดำเนินต่อไปจนกว่าจะมีเพียงหมายเลขที่เหลืออยู่เท่านั้น กำหนดการดำเนินการต่อไปนี้ในกอง:
Max-Heapify: ปรับโหนดปลายของกองเพื่อให้โหนดเด็กมีขนาดเล็กกว่าโหนดพาเรนต์เสมอ
สร้างกองสูงสุด (Build-Max-Heap): จัดลำดับข้อมูลทั้งหมดของกองเพื่อให้เป็นกองสูงสุด
HEAP-SORT: ลบโหนดรูทของข้อมูลแรกและดำเนินการเรียกซ้ำของการปรับฮีปสูงสุด
ก่อนที่จะดำเนินการอภิปรายต่อไปนี้ปัญหาหนึ่งที่ต้องระบุไว้คือ: อาร์เรย์ทั้งหมดเป็นศูนย์ซึ่งหมายความว่าโมเดลโครงสร้างข้อมูลฮีปของเราจะเปลี่ยนไป
(ศูนย์อิง)
ตามลำดับต้องมีการปรับสูตรการคำนวณหลายอย่างตาม:
ผู้ปกครอง (i) = ชั้น ((i-1)/2), ตัวห้อยโหนดพาเรนต์ของ i
ซ้าย (i) = 2i + 1, ตัวห้อยโหนดลูกซ้ายของ i
ขวา (i) = 2 (i + 1) ซึ่งเป็นตัวห้อยโหนดลูกที่ถูกต้องของ i
ฟังก์ชั่นของการปรับกองสูงสุด (MaxHeapify) คือการรักษาคุณสมบัติของกองที่ใหญ่ที่สุดและเป็นรูทีนย่อยหลักสำหรับการสร้างกองที่ใหญ่ที่สุด กระบวนการดำเนินการแสดงในรูป:
(Max-Heapify)
เนื่องจากกองยังคงละเมิดธรรมชาติของกองหลังจากการปรับครั้งเดียวจึงจำเป็นต้องมีการทดสอบแบบเรียกซ้ำเพื่อให้กองทั้งหมดเป็นไปตามธรรมชาติของกอง สามารถแสดงใน JavaScript ได้ดังนี้:
/** * ตรวจสอบจากดัชนีและรักษาคุณสมบัติฮีปสูงสุด * * @Array * * ดัชนีเริ่มต้นของการตรวจสอบ @Index * * @HeapSize ขนาดกอง * **/ฟังก์ชั่น maxHeapify (อาร์เรย์, ดัชนี, heapsize) {var imax = index, ileft = 2 * ดัชนี + 1, iright = 2 * (ดัชนี + 1); if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft; } if (iright <heapsize && array [imax] <array [iright]) {iMax = iright; } if (iMax! = index) {swap (array, iMax, index); MaxHeapify (อาร์เรย์, iMax, heapsize); // การปรับแบบเรียกซ้ำ}} การแลกเปลี่ยนฟังก์ชั่น (อาร์เรย์, i, j) {var temp = array [i]; อาร์เรย์ [i] = อาร์เรย์ [j]; อาร์เรย์ [j] = temp;}โดยทั่วไปการพูดซ้ำส่วนใหญ่ใช้ในวิธีการแบ่งและการรักษาและไม่จำเป็นต้องมีการแบ่งและการรักษาที่นี่ ยิ่งไปกว่านั้นการโทรแบบเรียกซ้ำจำเป็นต้องมีการกด/ล้างสแต็กซึ่งมีข้อเสียเล็กน้อยในการปฏิบัติงานเมื่อเทียบกับการทำซ้ำ แน่นอนว่าสิ่งนี้สามารถเพิกเฉยได้ตามกฎ 20/80 แต่ถ้าคุณคิดว่าการใช้การเรียกซ้ำจะทำให้คุณรู้สึกไม่สบายใจคุณสามารถใช้การวนซ้ำได้เช่นต่อไปนี้:
/** * ตรวจสอบจากดัชนีและรักษาคุณสมบัติฮีปสูงสุด * * @Array * * ดัชนีเริ่มต้นของการตรวจสอบ @Index * * @HeapSize ขนาดกอง * **/ฟังก์ชั่น maxHeapify (อาร์เรย์, ดัชนี, heapsize) {var iMax, Ileft, Iright; ในขณะที่ (จริง) {iMax = ดัชนี; ileft = 2 * ดัชนี + 1; iright = 2 * (ดัชนี + 1); if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft; } if (iright <heapsize && array [imax] <array [iright]) {iMax = iright; } if (iMax! = index) {swap (array, iMax, index); index = iMax; } else {break; }}} การแลกเปลี่ยนฟังก์ชั่น (อาร์เรย์, i, j) {var temp = array [i]; อาร์เรย์ [i] = อาร์เรย์ [j]; อาร์เรย์ [j] = temp;}จุดประสงค์ในการสร้างกองสูงสุด (Build-Max-Heap) คือการแปลงอาร์เรย์เป็นกองสูงสุดโดยยอมรับพารามิเตอร์สองตัวของอาร์เรย์และขนาดฮีป Build-Max-Heap จะเรียก Max-Heapify จากด้านล่างขึ้นไปเพื่อแปลงอาร์เรย์และสร้างกองสูงสุด เนื่องจาก Max-Heapify สามารถมั่นใจได้ว่าโหนดหลังจากการย่อยฉันตรงตามคุณสมบัติของกองที่ใหญ่ที่สุดการโทรจากล่างขึ้นบนไปยัง Max-Heapify สามารถรักษาคุณสมบัตินี้ได้ในระหว่างกระบวนการแปลง หากองค์ประกอบหมายเลขฮีปสูงสุดคือ N จากนั้น Build-Max-Heap เรียกใช้สูงสุดในลำดับจาก Parent (N) กระบวนการมีดังนี้:
คำอธิบายมีดังนี้ใน JavaScript:
ฟังก์ชั่น buildmaxheap (อาร์เรย์, heapsize) {var i, iparent = math.floor ((heapsize - 1) / 2); สำหรับ (i = iParent; i> = 0; i--) {maxHeapify (อาร์เรย์, i, heapsize); -Heap-Sort เป็นอัลกอริทึมอินเตอร์เฟสสำหรับการเรียงลำดับฮีป ฮีป-เรียงลำดับแรกเรียกว่า-แม็กซ์ฮีปเพื่อแปลงอาร์เรย์เป็นกองสูงสุดจากนั้นแลกเปลี่ยนองค์ประกอบด้านบนและด้านล่างของกองจากนั้นก็เพิ่มขึ้นด้านล่างและในที่สุดก็เรียก Max-Heapify เพื่อรักษาคุณสมบัติกองสูงสุด เนื่องจากองค์ประกอบด้านบนของกองจะต้องเป็นองค์ประกอบที่ใหญ่ที่สุดในกองหลังจากการดำเนินการหนึ่งองค์ประกอบที่ใหญ่ที่สุดที่มีอยู่ในฮีปจะถูกแยกออกจากกองออกจากกองและหลังจาก N-1 ครั้งซ้ำแล้วซ้ำอีก กระบวนการทั้งหมดมีดังนี้:
คำอธิบายมีดังนี้ใน JavaScript:
ฟังก์ชั่น heapsort (อาร์เรย์, heapsize) {buildmaxheap (อาร์เรย์, heapsize); สำหรับ (int i = heapsize-1; i> 0; i--) {swap (อาร์เรย์, 0, i); MaxHeapify (อาร์เรย์, 0, i); -4. การใช้ภาษา JavaScript
ในที่สุดจัดระเบียบด้านบนเป็นรหัส JavaScript ที่สมบูรณ์ดังนี้:
ฟังก์ชั่น heapsort (อาร์เรย์) {ฟังก์ชั่นแลกเปลี่ยน (อาร์เรย์, i, j) {var temp = array [i]; อาร์เรย์ [i] = อาร์เรย์ [j]; อาร์เรย์ [j] = อุณหภูมิ; } ฟังก์ชั่น MaxHeapify (อาร์เรย์, ดัชนี, heapsize) {var imax, ileft, iright; ในขณะที่ (จริง) {iMax = ดัชนี; ileft = 2 * ดัชนี + 1; iright = 2 * (ดัชนี + 1); if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft; } if (iright <heapsize && array [imax] <array [iright]) {iMax = iright; } if (iMax! = index) {swap (array, iMax, index); index = iMax; } else {break; }}} ฟังก์ชั่น buildMaxHeap (อาร์เรย์) {var i, iParent = math.floor (array.length / 2) - 1; สำหรับ (i = iParent; i> = 0; i--) {maxHeapify (อาร์เรย์, i, array.length); }} การเรียงลำดับฟังก์ชัน (อาร์เรย์) {buildMaxHeap (อาร์เรย์); สำหรับ (var i = array.length-1; i> 0; i--) {swap (array, 0, i); MaxHeapify (อาร์เรย์, 0, i); } return array; } return sort (array);}5. แอปพลิเคชันของอัลกอริทึมการเรียงลำดับฮีป
(1) ประสิทธิภาพ/ความซับซ้อนของอัลกอริทึม
ความซับซ้อนของเวลาของการเรียงลำดับฮีปมีความเสถียรมาก (เราเห็นได้ว่ามันไม่ไวต่อข้อมูลอินพุต) และความซับซ้อนของ O (NN) กรณีที่ดีที่สุดคือกรณีที่เลวร้ายที่สุด
อย่างไรก็ตามความซับซ้อนเชิงพื้นที่แตกต่างกันไปตามการใช้งาน ข้างต้นกล่าวถึงความซับซ้อนทั่วไปสองประการ: O (n) และ O (1) ตามหลักการของการประหยัดพื้นที่ฉันแนะนำวิธีความซับซ้อน O (1)
(2) ความเสถียรของอัลกอริทึม
มีกระบวนการกรองและการเคลื่อนไหวจำนวนมากในการเรียงลำดับฮีปซึ่งเป็นของอัลกอริทึมการเรียงลำดับที่ไม่เสถียร
(3) สถานการณ์อัลกอริทึมที่ใช้งานได้
การเรียงลำดับของกองจะมีค่าใช้จ่ายค่อนข้างใหญ่ในกระบวนการสร้างกองและปรับกองและไม่สามารถใช้งานได้เมื่อมีองค์ประกอบน้อย อย่างไรก็ตามเมื่อมีองค์ประกอบหลายอย่างก็ยังเป็นตัวเลือกที่ดี โดยเฉพาะอย่างยิ่งเมื่อการแก้ปัญหาเช่น "จำนวนอันดับต้น ๆ n ใหญ่" มันเกือบจะเป็นอัลกอริทึมที่ต้องการ