1. ความรู้พื้นฐาน
สิ่งที่เรามักเรียกว่ากองหมายถึงกองไบนารีซึ่งเรียกว่าต้นไม้ไบนารีที่สมบูรณ์หรือต้นไม้ไบนารีที่สมบูรณ์โดยประมาณ กองไบนารีแบ่งออกเป็นกองที่ใหญ่ที่สุดและกองที่เล็กที่สุด
การเรียงลำดับฮีปหมายถึงอัลกอริทึมการเรียงลำดับที่ออกแบบมาโดยใช้โครงสร้างข้อมูลฮีปซึ่งเป็นการเลือกการเรียงลำดับ คุณสามารถค้นหาองค์ประกอบของดัชนีที่ระบุได้อย่างรวดเร็วโดยใช้คุณสมบัติของอาร์เรย์ อาร์เรย์สามารถรับองค์ประกอบโดยตรงตามดัชนีและความซับซ้อนของเวลาคือ O (1) นั่นคือค่าคงที่ดังนั้นจึงมีประสิทธิภาพอย่างมากสำหรับการได้มาซึ่งมูลค่า
ลักษณะของกองสูงสุดมีดังนี้:
ลักษณะของกองขั้นต่ำมีดังนี้:
2. อัลกอริทึมคิด
1. แนวคิดอัลกอริทึมของกองที่ใหญ่ที่สุดคือ:
ก่อนอื่น R [0 … N-1] ถูกสร้างขึ้นในกองที่ใหญ่ที่สุด ในเวลานี้มันเป็นกองที่ไม่ได้เรียงลำดับ ฮีปด้านบนเป็นองค์ประกอบที่ใหญ่ที่สุดและจากนั้นบันทึกสุดท้าย R [N-1] ของพื้นที่ที่ไม่ได้เรียงลำดับจะถูกแลกเปลี่ยน สิ่งนี้ส่งผลให้พื้นที่ใหม่ที่ไม่มีการเรียงลำดับ r [0 … n-2] และพื้นที่ที่สั่งซื้อ r [n-1] และตอบสนอง r [0 … n-2] .keys ≤ r [n-1]
เนื่องจาก R [0 … N-2] แรกอาจไม่เป็นไปตามคุณสมบัติของกองสูงสุดหลังจากการแลกเปลี่ยน R [0 … N-2] แรกจะถูกปรับให้เป็นกองสูงสุดจนกระทั่งมีการปรับองค์ประกอบสุดท้ายของ R [0]
หลังจากการเรียงลำดับสูงสุดของฮีปเสร็จสมบูรณ์จริง ๆ แล้วมันเป็นลำดับจากน้อยไปมาก ทุกครั้งที่มีการปรับฮีปองค์ประกอบที่ใหญ่ที่สุดจะได้รับจากนั้นแลกเปลี่ยนกับองค์ประกอบสุดท้ายของกองปัจจุบัน ดังนั้นลำดับสุดท้ายที่ได้รับคือลำดับจากน้อยไปมาก
2. แนวคิดอัลกอริทึมของกองเล็กที่สุดคือ:
ก่อนอื่น R [0 … N-1] ถูกสร้างขึ้นในกองที่เล็กที่สุด ในเวลานี้มันเป็นกองที่ไม่ได้เรียงลำดับ องค์ประกอบด้านบนของกองเป็นองค์ประกอบที่เล็กที่สุดจากนั้นแลกเปลี่ยน R [0] กับ R [N-1] สุดท้ายของพื้นที่ที่ไม่ได้เรียงลำดับดังนั้นจึงได้รับกองใหม่ที่ไม่ได้เรียงลำดับ R [0 … N-2]
เนื่องจาก R [0 … N-2] แรกอาจไม่ตรงกับคุณสมบัติของกองขั้นต่ำหลังจากการแลกเปลี่ยน R [0 … N-2] แรกจะถูกปรับให้เป็นกองขั้นต่ำจนกระทั่งมีการปรับองค์ประกอบสุดท้ายของ R [0] หลังจากการสั่งซื้อของกองขั้นต่ำเสร็จสมบูรณ์จริง ๆ แล้วมันเป็นลำดับจากมากไปน้อย ทุกครั้งที่มีการปรับฮีปองค์ประกอบที่เล็กที่สุดจะได้รับจากนั้นแลกเปลี่ยนกับองค์ประกอบสุดท้ายของกองที่ไม่ได้เรียงลำดับในปัจจุบันดังนั้นลำดับที่ได้รับจะอยู่ในลำดับจากมากไปน้อย
เคล็ดลับ: กระบวนการจัดเรียงฮีปเป็นกระบวนการของการขยายพื้นที่ที่สั่งซื้ออย่างต่อเนื่องและจากนั้นลดพื้นที่ที่ไม่เป็นระเบียบอย่างต่อเนื่องจนกว่าจะมีพื้นที่สั่งซื้อเท่านั้น
3. การวิเคราะห์กระบวนการจัดเรียง
เนื่องจากอัลกอริทึมค่อนข้างเป็นนามธรรมที่นี่เราจึงแสดงกระบวนการเรียงลำดับฮีปโดยตรงโดยให้ตัวอย่างเล็ก ๆ น้อย ๆ ต่อไปเราใช้ลำดับที่ไม่ได้เรียงลำดับนี้เพื่อใช้กองที่ใหญ่ที่สุดสำหรับการเรียงลำดับฮีปและลำดับผลลัพธ์คือลำดับจากน้อยไปหามาก (ASC)
ลำดับที่ไม่ได้เรียงลำดับ: 89, -7,999, -89,7,0, -888,7, -7, -89,7,0, -888,7, -7, -7
ขั้นตอนที่ 1: เริ่มต้นกองสูงสุดเพื่อสร้าง:
ขั้นตอนที่ 2: แลกเปลี่ยนองค์ประกอบสูงสุด 999 ที่ด้านบนของกองด้วยองค์ประกอบสุดท้ายของพื้นที่ที่ไม่ได้เรียงลำดับเพื่อให้ 999 กลายเป็นพื้นที่ที่สั่งซื้อ หลังจากแลกเปลี่ยน -7 กลายเป็นกองซุป เนื่องจาก -7 ไม่ใช่องค์ประกอบที่ใหญ่ที่สุดในพื้นที่ที่ไม่ได้เรียงลำดับจึงจำเป็นต้องปรับพื้นที่ที่ไม่ได้เรียงลำดับเพื่อให้ค่าสูงสุด 89 ในพื้นที่ที่ไม่ได้เรียงลำดับกลายเป็นกองบนสุดดังนั้นจึงมีการแลกเปลี่ยน -7 และ 89 หลังจากการแลกเปลี่ยนทรีย่อยที่ถูกต้องของ 89 ไม่ตรงกับคุณสมบัติของกองที่ใหญ่ที่สุดดังนั้นทรีย่อยที่ถูกต้องจะต้องปรับเป็นกองที่ใหญ่ที่สุดดังนั้น -7 จะต้องแลกเปลี่ยนกับ 0 ดังแสดงในรูปด้านล่าง:
จากรูปเมื่อ -7% 89% การแลกเปลี่ยนด้านบนของกองเป็นองค์ประกอบที่ใหญ่ที่สุด แต่ลูกซ้ายของ -7 คือ 0 และเด็กที่เหมาะสมคือ -888 ตั้งแต่ -7 <0 โหนด -7 ไม่ตรงกับคุณสมบัติของกองดังนั้นจึงต้องมีการปรับ ดังนั้น 0 ถูกแลกเปลี่ยนกับ -7
จากนั้นทำซ้ำขั้นตอนที่สองจนกว่าจะกลายเป็นพื้นที่ที่สั่งซื้อ
ในที่สุด: สิ่งที่ได้รับคือลำดับจากน้อยไปมาก
4. ความซับซ้อนของเวลา
เวลาของการเรียงลำดับกองส่วนใหญ่ประกอบด้วยเวลาค่าใช้จ่ายของการสร้างกองเริ่มต้นและปรับกองซ้ำ ๆ เนื่องจากการเรียงลำดับของฮีปไม่เสถียรเวลาที่ซับซ้อนเวลาจะได้รับมากขึ้นตามสถานการณ์จริงดังนั้นจึงสามารถใช้ความซับซ้อนของเวลาเฉลี่ยเท่านั้น
ความซับซ้อนของเวลาเฉลี่ยคือ: o (n * log2 (n))
การดำเนินการที่ใช้เวลานานของการเรียงลำดับฮีปรวมถึง: กองเริ่มต้น + การปรับซ้ำของกองซ้ำและความซับซ้อนของเวลามีดังนี้:
1. การสร้างกองเริ่มต้น: โหนดหลักแต่ละโหนดจะเปรียบเทียบและแลกเปลี่ยนกับโหนดลูกซ้ายและขวาได้สูงสุด 2 ครั้งดังนั้นความซับซ้อนจึงเกี่ยวข้องกับจำนวนโหนดหลัก ขึ้นอยู่กับ 2x <= n (x คือจำนวนครั้งที่องค์ประกอบ N สามารถพับได้ครึ่งหนึ่งนั่นคือจำนวนโหนดหลัก) จะได้รับ x = log2n นั่นคือ o (log2n)
2. การปรับซ้ำ ๆ ของกอง: เนื่องจากผลการเปรียบเทียบอาเรย์ถูกบันทึกไว้ในระหว่างการเริ่มต้นของฮีปการเรียงลำดับฮีปจึงไม่ไวต่อลำดับของอาร์เรย์ของลำดับดั้งเดิมและสถานการณ์ที่ดีที่สุดคล้ายกับกรณีที่เลวร้ายที่สุด องค์ประกอบด้านบนของฮีปจะต้องสกัด N-1 ครั้ง ทุกครั้งที่มีการใช้องค์ประกอบฮีปด้านบนจะต้องสร้างฮีปใหม่ (O (reconstruct heap) <o (กองเริ่มต้น)) น้อยกว่า o (n-1) * o (log2n)
การใช้งานที่แนะนำ:
เนื่องจากจำนวนครั้งที่การเริ่มต้นของฮีปจำเป็นต้องเปรียบเทียบการเรียงลำดับฮีปจึงเหมาะสำหรับสถานการณ์ที่ปริมาณข้อมูลมีขนาดใหญ่มาก (ข้อมูลล้านหรือมากกว่า) เนื่องจากการเรียงลำดับอย่างรวดเร็วอย่างมีประสิทธิภาพขึ้นอยู่กับการใช้งานแบบเรียกซ้ำได้ข้อผิดพลาดของสแต็กล้นเกิดขึ้นเมื่อปริมาณข้อมูลมีขนาดใหญ่มาก
5. รหัสตัวอย่าง Java
Public Class Heapsort {Private Static Int [] sort = new int [] {1,0,10,20,3,5,6,4,9,9,8,12, 17,34,11}; โมฆะคงที่สาธารณะหลัก (สตริง [] args) {buildmaxheapify (เรียงลำดับ); heapsort (เรียงลำดับ); พิมพ์ (เรียงลำดับ); } โมฆะคงที่ส่วนตัว buildMaxHeapify (int [] data) {// เฉพาะผู้ที่ไม่มีลูกเท่านั้นที่ต้องสร้างกองสูงสุดเริ่มจากโหนดพาเรนต์สุดท้าย int startIndex = getParentIndex (data.length-1); // สร้างกองสูงสุดจากจุดสิ้นสุด }} / ***สร้างฮีปสูงสุด**@paramdata*@paramheapsize ต้องการขนาดของกองสูงสุดซึ่งโดยทั่วไปจะใช้ในการเรียงลำดับเนื่องจากค่าสูงสุดจะถูกวางไว้ที่จุดสิ้นสุด ดัชนี) {// เปรียบเทียบจุดปัจจุบันกับโหนดลูกซ้ายและขวา int int ซ้าย = getChildleftIndex (ดัชนี); int ขวา = getChildrightIndex (ดัชนี); int ที่ใหญ่ที่สุด = ดัชนี; if (ซ้าย <heapsize && data [index] <data [ซ้าย]) {ใหญ่ที่สุด = ซ้าย; } if (ขวา <heapsize && data [ใหญ่ที่สุด] <data [ขวา]) {ใหญ่ที่สุด = ขวา; } // หลังจากได้รับค่าสูงสุดแล้วอาจต้องมีการแลกเปลี่ยน หากแลกเปลี่ยนเด็ก ๆ อาจไม่ใช่กองที่ใหญ่ที่สุด จะต้องมีการปรับใหม่ถ้า (ใหญ่ที่สุด! = ดัชนี) {int temp = data [index]; ข้อมูล [ดัชนี] = ข้อมูล [ใหญ่ที่สุด]; ข้อมูล [ใหญ่ที่สุด] = อุณหภูมิ; MaxHeapify (ข้อมูล, heapsize, ใหญ่ที่สุด); }} /***การเรียงลำดับค่าสูงสุดจะถูกวางไว้ที่ส่วนท้าย แม้ว่าข้อมูลจะเป็นกองที่ใหญ่ที่สุด แต่มันก็จะเพิ่มขึ้นหลังจากการเรียงลำดับ * *@paramdata */โมฆะคงที่ heapsort (int [] ข้อมูล) {// แลกเปลี่ยนกับส่วนหัวในตอนท้ายปรับค่าสูงสุดหลังจากแลกเปลี่ยน (int i = data.length-1; i> 0; i-) {int temp = data ข้อมูล [0] = ข้อมูล [i]; ข้อมูล [i] = อุณหภูมิ; MaxHeapify (ข้อมูล, i, 0); }} / ** *paramcurrent *@return * / ส่วนตัวคงที่ int getParentIndex (int ปัจจุบัน) {return (current-1) >> 1; } / ** *นำเสนอตำแหน่งโหนดลูกให้ความสนใจกับวงเล็บและลำดับความสำคัญการเพิ่มคือสูงกว่า * *@paramcurrent *@return * / ส่วนตัวคงที่ int getChildleftIndex (กระแส int) {return (ปัจจุบัน << 1) +1; } / ** *ตำแหน่งโหนดลูกขวา * *@paramcurrent *@return * / ส่วนตัวคงที่ int getChildrightIndex (int ปัจจุบัน) {return (ปัจจุบัน << 1) +2; } การพิมพ์โมฆะแบบคงที่ส่วนตัว (int [] data) {int pre = -2; สำหรับ (int i = 0; i <data.length; i ++) {ถ้า (pre <(int) getLog (i+1)) {pre = (int) getLog (i+1); System.out.println (); } system.out.print (data [i]+"|"); }}/** *โลโก้ที่มีฐาน 2 * *@paraparam *@return */ส่วนตัวคงที่ double getLog (คู่พารามิเตอร์) {return math.log (param) /math.log (2); -