ฮีปเรียกว่า 'เรียงลำดับบางส่วน' ไม่ใช่ 'เรียงลำดับบางส่วน' คำว่า 'sort' หมายถึงการเรียงลำดับที่สมบูรณ์ (การเรียงลำดับแบบสมบูรณ์) ฮีปไม่ได้รับคำสั่งบางส่วนโดยพลการ ฮีปถูกจัดเรียงบางส่วนตามเกณฑ์ (รูปแบบ) ดังที่แสดงด้านล่าง
ดังนั้น heapsort ประกอบด้วยสองขั้นตอน: การสร้างฮีปและการแยกองค์ประกอบที่เรียงลำดับจากด้านบนของฮีป ในขั้นตอนที่สอง หลังจากการแยกแต่ละครั้ง ฮีปจะถูกสร้างขึ้นใหม่ การสร้างใหม่แต่ละครั้งจะเร็วกว่ากระบวนการสร้างเดิม เนื่องจากการสร้างใหม่เสร็จสิ้นจากโครงสร้างก่อนหน้า โดยที่องค์ประกอบหนึ่งถูกลบออกไป และด้วยเหตุนี้ heapsort จะเรียงลำดับรายการที่ไม่เรียงลำดับทั้งหมด
จุดมุ่งหมายของบทความนี้คือการอธิบายสั้น ๆ เกี่ยวกับ heapsort และสร้างความซับซ้อนของเวลา (ดูความหมายของความซับซ้อนของเวลาด้านล่าง) ในตอนท้ายการเข้ารหัสจะทำใน C ++
ฮีปขั้นต่ำ
ฮีปอาจเป็นฮีปขั้นต่ำหรือฮีปสูงสุดก็ได้ max-heap เป็นองค์ประกอบที่องค์ประกอบแรกเป็นองค์ประกอบสูงสุด และต้นไม้ทั้งหมดหรือรายการที่เกี่ยวข้องจะถูกเรียงลำดับบางส่วนในลำดับจากมากไปน้อย min-heap เป็นองค์ประกอบที่องค์ประกอบแรกเป็นองค์ประกอบที่น้อยที่สุด และรายการทั้งหมดถูกเรียงลำดับบางส่วนในลำดับจากน้อยไปมาก ในบทความนี้จะพิจารณาเฉพาะฮีปขั้นต่ำเท่านั้น หมายเหตุ: ในหัวข้อของฮีป องค์ประกอบเรียกอีกอย่างว่าโหนด
ฮีปเป็นต้นไม้ไบนารีที่สมบูรณ์ ต้นไม้ไบนารีสามารถแสดงเป็นอาร์เรย์ (รายการ); อ่านจากบนลงล่างและซ้ายไปขวา คุณสมบัติฮีปสำหรับฮีปขั้นต่ำคือโหนดหลักมีค่าน้อยกว่าหรือเท่ากับลูกๆ สองตัวแต่ละตัว ตัวอย่างของรายการที่ไม่เรียงลำดับคือ:
| 9 | 19 | 24 | 5 | 3 | สิบเอ็ด | 14 | 22 | 7 | 6 | 17 | สิบห้า | โมฆะ | โมฆะ | โมฆะ |
| 0 | 1 | สอง | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | สิบเอ็ด | 12 | 13 | 14 |
แถวแรกของตารางนี้คือองค์ประกอบของอาร์เรย์ ในแถวที่สองคือดัชนีแบบอิงศูนย์ รายการองค์ประกอบนี้สามารถแสดงเป็นต้นไม้ได้ เพิ่มองค์ประกอบ null เพื่อสร้างไบนารีทรีแบบเต็ม พูดอย่างเคร่งครัด องค์ประกอบ null ไม่ได้เป็นส่วนหนึ่งของรายการ (ต้นไม้) รายการนี้ไม่มีการสั่งซื้อ ดังนั้นจึงยังไม่เป็นฮีป มันจะกลายเป็นกองเมื่อมีการสั่งซื้อบางส่วนตามคุณสมบัติของฮีป
ความสัมพันธ์ระหว่างโหนดและดัชนี
โปรดจำไว้ว่า ฮีปเป็นไบนารีทรีที่สมบูรณ์ก่อนที่จะมีการกำหนดค่าฮีป (คุณสมบัติฮีป) รายการก่อนหน้านี้ยังไม่เป็นฮีป เนื่องจากอิลิเมนต์ไม่เชื่อฟังคุณสมบัติฮีป มันจะกลายเป็นฮีปหลังจากจัดเรียงองค์ประกอบใหม่เป็นลำดับบางส่วนตามคุณสมบัติ min-heap การเรียงลำดับบางส่วนสามารถมองเห็นเป็นการเรียงลำดับบางส่วน (แม้ว่าคำว่า 'การเรียงลำดับ' หมายถึงการเรียงลำดับที่สมบูรณ์)
ไม่ว่าไบนารีทรีจะเป็นฮีปหรือไม่ก็ตาม พาเรนต์แต่ละคนมีลูกสองคน ยกเว้นโหนดลีฟ (สุดท้าย) มีความสัมพันธ์ทางคณิตศาสตร์ระหว่างดัชนีระหว่างผู้ปกครองแต่ละคนกับเด็ก เป็นดังนี้: หากพาเรนต์อยู่ที่ดัชนี i ลูกด้านซ้ายจะอยู่ที่ดัชนี:
สอง * ผม + 1และลูกที่ถูกต้องอยู่ที่ดัชนี:
สอง * ผม + สองนี่สำหรับการจัดทำดัชนีแบบอิงศูนย์ ดังนั้น parent ที่ index 0 จึงมี child ทางซ้ายที่ index 2×0+1=1 และ child ขวาที่ 2×0+2=2 ผู้ปกครองที่ดัชนี 1 มีลูกซ้ายที่ดัชนี 2×1+1=3 และลูกขวาที่ดัชนี 2×1+2=4; และอื่นๆ
โดยคุณสมบัติ min-heap พาเรนต์ที่ i น้อยกว่าหรือเท่ากับชายด์ด้านซ้ายที่ 2i+1 และน้อยกว่าหรือเท่ากับชายด์ด้านขวาที่ 2i+2
กอง
Heapifying ความหมายคือ การสร้างกอง หมายถึงการจัดเรียงองค์ประกอบของรายการ (หรือแผนผังที่เกี่ยวข้อง) เพื่อให้เป็นไปตามคุณสมบัติของฮีป ในตอนท้ายของกระบวนการฮีป รายการหรือทรีจะเป็นฮีป
หากรายการที่ไม่เรียงลำดับก่อนหน้าถูกฮีป มันจะกลายเป็น:
| 3 | 5 | สิบเอ็ด | 7 | 6 | สิบห้า | 14 | 22 | 9 | 19 | 17 | 24 | โมฆะ | โมฆะ | โมฆะ |
| 0 | 1 | สอง | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | สิบเอ็ด | 12 | 13 | 14 |
หมายเหตุ: มีองค์ประกอบ 12 รายการและไม่ใช่ 15 รายการในรายการ ในแถวที่สองคือดัชนี ในกระบวนการสร้างกอง จะต้องตรวจสอบองค์ประกอบและเปลี่ยนบางส่วน
สังเกตว่าองค์ประกอบที่เล็กที่สุดและองค์ประกอบแรกคือ 3 องค์ประกอบที่เหลือจะตามมาในลักษณะที่ขึ้นแต่เป็นลูกคลื่น ถ้าลูกซ้ายและขวาที่ตำแหน่ง 2i+1 และ 2i+2 มีค่ามากกว่าหรือเท่ากับพาเรนต์ที่ i นี่จะเป็นฮีปขั้นต่ำ นี่ไม่ใช่การสั่งซื้อหรือการเรียงลำดับแบบเต็ม นี่คือการสั่งซื้อบางส่วนตามคุณสมบัติของฮีป จากที่นี่ ขั้นตอนต่อไปสำหรับการเรียงลำดับฮีปเริ่มต้นขึ้น
Heapify Time Complexity
ความซับซ้อนของเวลาคือเวลาทำงานที่สัมพันธ์กันของบางรหัส มันสามารถเห็นได้ว่าเป็นจำนวนของการดำเนินการหลักสำหรับรหัสนั้นให้เสร็จสมบูรณ์ มีอัลกอริธึมที่แตกต่างกันสำหรับการสร้างฮีป รายการที่มีประสิทธิภาพและเร็วที่สุดอย่างต่อเนื่องจะแบ่งรายการออกเป็นสองส่วน ตรวจสอบองค์ประกอบจากด้านล่าง จากนั้นจึงทำการสลับองค์ประกอบ ให้ N เป็นจำนวนองค์ประกอบที่ใช้งานได้จริงในรายการ ด้วยอัลกอริธึมนี้ จำนวนสูงสุดของการดำเนินการหลัก (การสลับ) คือ N ความซับซ้อนของเวลาสำหรับการฮีปถูกกำหนดให้ก่อนหน้านี้เป็น:
อู๋ ( น )โดยที่ n คือ N และเป็นจำนวนสูงสุดของการดำเนินการหลักที่เป็นไปได้ สัญกรณ์นี้เรียกว่าสัญกรณ์บิ๊กโอ เริ่มต้นด้วย O เป็นตัวพิมพ์ใหญ่ ตามด้วยวงเล็บ ภายในวงเล็บคือนิพจน์สำหรับจำนวนการดำเนินการสูงสุดที่เป็นไปได้
ข้อควรจำ: การบวกสามารถกลายเป็นการคูณได้หากสิ่งเดียวกันถูกเพิ่มเข้ามาซ้ำๆ
Heapsort ภาพประกอบ
รายการที่ไม่เรียงลำดับก่อนหน้านี้จะใช้เพื่อแสดงฮีพซอร์ต รายการที่กำหนดคือ:
9 19 24 5 3 สิบเอ็ด 14 22 7 6 17 สิบห้าmin-heap ที่ผลิตจากรายการคือ:
3 5 สิบเอ็ด 7 6 สิบห้า 14 22 9 19 17 24ขั้นตอนแรกใน heapsort คือการผลิตกองที่ผลิตขึ้น นี่คือรายการที่สั่งซื้อบางส่วน ไม่ใช่รายการที่เรียงลำดับ (เรียงลำดับทั้งหมด)
ขั้นตอนที่สองประกอบด้วยการลบองค์ประกอบที่น้อยที่สุดซึ่งเป็นองค์ประกอบแรกออกจากฮีปการฮีปที่เหลืออีกครั้งและการลบองค์ประกอบที่น้อยที่สุดในผลลัพธ์ องค์ประกอบที่น้อยที่สุดจะเป็นองค์ประกอบแรกในฮีปที่ฮีปซ้ำเสมอ องค์ประกอบจะไม่ถูกลบออกและโยนทิ้งไป สามารถส่งไปยังอาร์เรย์อื่นในลำดับที่จะถูกลบออก
ในท้ายที่สุด อาร์เรย์ใหม่จะมีการจัดเรียงองค์ประกอบทั้งหมด (ทั้งหมด) ตามลำดับจากน้อยไปมาก และไม่ได้สั่งเพียงบางส่วนอีกต่อไป
ในขั้นตอนที่สอง สิ่งแรกที่ต้องทำคือลบ 3 และวางไว้ในอาร์เรย์ใหม่ ผลลัพธ์คือ:
3และ
5 สิบเอ็ด 7 6 สิบห้า 14 22 9 19 17 24องค์ประกอบที่เหลือจะต้องถูกฮีปก่อนที่จะแยกองค์ประกอบแรก กององค์ประกอบที่เหลือสามารถกลายเป็น:
5 6 7 9 สิบห้า 14 22 สิบเอ็ด 19 17 24การแยก 5 และเพิ่มไปยังรายการใหม่ (อาร์เรย์) ให้ผลลัพธ์:
3 5และ
6 7 9 สิบห้า 14 22 สิบเอ็ด 19 17 24Heapifying ชุดที่เหลือจะให้:
6 7 9 สิบห้า 14 22 สิบเอ็ด 19 17 24การแยก 6 และเพิ่มไปยังรายการใหม่ (อาร์เรย์) ให้ผลลัพธ์:
3 5 6และ
7 9 สิบห้า 14 22 สิบเอ็ด 19 17 24Heapifying ชุดที่เหลือจะให้:
7 9 สิบเอ็ด 14 22 สิบห้า 19 17 24การแยก 7 และเพิ่มลงในรายการใหม่จะให้ผลลัพธ์:
3 5 6 7และ
9 สิบเอ็ด 14 22 สิบห้า 19 17 24Heapifying ชุดที่เหลือให้:
9 สิบเอ็ด 14 22 สิบห้า 19 17 24แยก 9 และเพิ่มในรายการใหม่ ให้ผลลัพธ์:
3 5 6 7 9และ
สิบเอ็ด 14 22 สิบห้า 19 17 24Heapifying ชุดที่เหลือให้:
สิบเอ็ด 14 17 สิบห้า 19 22 24การแยก 11 และเพิ่มลงในรายการใหม่จะให้ผลลัพธ์:
3 5 6 7 9 สิบเอ็ดและ
14 17 สิบห้า 19 22 24Heapifying ชุดที่เหลือจะให้:
14 17 สิบห้า 19 22 24การแยก 14 และเพิ่มลงในรายการใหม่จะให้ผลลัพธ์:
3 5 6 7 9 สิบเอ็ด 14และ
17 สิบห้า 19 22 24Heapifying ชุดที่เหลือจะให้:
สิบห้า 17 19 22 24การแยก 15 และเพิ่มลงในรายการใหม่จะให้ผลลัพธ์:
3 5 6 7 9 สิบเอ็ด 14 สิบห้าและ
17 19 22 24Heapifying ชุดที่เหลือจะให้:
17 19 22 24การแยก 17 และเพิ่มลงในรายการใหม่จะให้ผลลัพธ์:
3 5 6 7 9 สิบเอ็ด 14 สิบห้า 17และ
19 22 24Heapifying ชุดที่เหลือจะให้:
19 22 24การแยก 19 และเพิ่มลงในรายการใหม่จะให้ผลลัพธ์:
3 5 6 7 9 สิบเอ็ด 14 สิบห้า 17 19และ
22 24Heapifying ชุดที่เหลือให้:
22 24การแยก 22 และเพิ่มลงในรายการใหม่จะให้ผลลัพธ์:
3 5 6 7 9 สิบเอ็ด 14 สิบห้า 17 19 22และ
24Heapifying ชุดที่เหลือให้:
24การแยก 24 และเพิ่มลงในรายการใหม่จะให้ผลลัพธ์:
3 5 6 7 9 สิบเอ็ด 14 สิบห้า 17 19 22 24และ
- - -ตอนนี้อาร์เรย์ฮีปว่างเปล่า องค์ประกอบทั้งหมดที่มีในตอนเริ่มต้นอยู่ในอาร์เรย์ใหม่ (รายการ) และจัดเรียงแล้ว
อัลกอริธึม Heapsort
แม้ว่าผู้อ่านอาจเคยอ่านในหนังสือเรียนที่ heapsort ประกอบด้วยสองขั้นตอน แต่ heapsort ยังคงถูกมองว่าประกอบด้วยขั้นตอนเดียว ซึ่งจะลดขนาดอาร์เรย์ที่กำหนดซ้ำแล้วซ้ำอีก ด้วยเหตุนี้ อัลกอริทึมในการจัดเรียงด้วย heapsort มีดังนี้:
- Heapify รายการที่ไม่ได้เรียงลำดับ
- แยกองค์ประกอบแรกของฮีปและใส่เป็นองค์ประกอบแรกของรายการใหม่
- Heapify รายการที่เหลือ
- แยกองค์ประกอบแรกของฮีปใหม่และใส่เป็นองค์ประกอบถัดไปของรายการใหม่
- ทำซ้ำขั้นตอนก่อนหน้าตามลำดับจนกว่ารายการฮีพจะว่างเปล่า ในท้ายที่สุด รายการใหม่จะถูกจัดเรียง
Heapsort Time Complexity ที่เหมาะสม
วิธีการแบบขั้นตอนเดียวใช้เพื่อกำหนดความซับซ้อนของเวลาสำหรับ heapsort สมมติว่ามีองค์ประกอบที่ไม่ได้เรียงลำดับ 8 รายการที่จะจัดเรียง
จำนวนการดำเนินการสูงสุดที่เป็นไปได้ในการฮีป 8 องค์ประกอบคือ 8 .ดิ จำนวนการดำเนินการสูงสุดที่เป็นไปได้ในการฮีปส่วนที่เหลือ 7 องค์ประกอบคือ 7 .
ดิ จำนวนการดำเนินการสูงสุดที่เป็นไปได้ในการฮีปส่วนที่เหลือ 6 องค์ประกอบคือ 6 .
ดิ จำนวนการดำเนินการสูงสุดที่เป็นไปได้ในการฮีปส่วนที่เหลือ 5 องค์ประกอบคือ 5 .
ดิ จำนวนการดำเนินการสูงสุดที่เป็นไปได้ในการฮีปส่วนที่เหลือ 4 องค์ประกอบคือ 4 .
ดิ จำนวนการดำเนินการสูงสุดที่เป็นไปได้ในการฮีปส่วนที่เหลือ 3 องค์ประกอบคือ 3 .
ดิ จำนวนการดำเนินการสูงสุดที่เป็นไปได้ในการฮีปส่วนที่เหลือ สอง องค์ประกอบคือ สอง .
ดิ จำนวนการดำเนินการสูงสุดที่เป็นไปได้ในการฮีปส่วนที่เหลือ 1 องค์ประกอบคือ 1 .
จำนวนการดำเนินการสูงสุดที่เป็นไปได้คือ:
8 + 7 + 6 + 5 + 4 + 3 + สอง + 1 = 36ค่าเฉลี่ยของจำนวนการดำเนินการเหล่านี้คือ:
36 / 8 = 4.5ขอให้สังเกตว่าสี่ฮีปสุดท้ายในภาพประกอบก่อนหน้านี้ไม่เปลี่ยนแปลง เมื่อองค์ประกอบแรกถูกลบออก ฮีปก่อนหน้านี้บางส่วนไม่เปลี่ยนแปลงเมื่อองค์ประกอบแรกถูกลบออก ด้วยเหตุนี้ จำนวนการดำเนินการหลัก (สวอป) โดยเฉลี่ยที่ดีขึ้นคือ 3 ไม่ใช่ 4.5 ดังนั้น จำนวนการดำเนินการหลักโดยรวมที่ดีกว่าคือ:
24 = 8 x 3=> 24 = 8 x บันทึก < ย่อย > สอง < / ย่อย > 8
ตั้งแต่ล็อก สอง 8 = 3
โดยทั่วไป ความซับซ้อนของเวลากรณีเฉลี่ยสำหรับ heapsort คือ:
โอ ( น. log2n )โดยที่จุดหมายถึงการคูณและ n คือ N จำนวนองค์ประกอบทั้งหมดในรายการ (รายการใดรายการหนึ่ง)
โปรดทราบว่าการดำเนินการแยกองค์ประกอบแรกจะถูกละเว้น ในหัวข้อ Time Complexity การดำเนินการที่ใช้เวลาค่อนข้างสั้นจะถูกละเว้น
การเข้ารหัสใน C++
ในไลบรารีอัลกอริทึมของ C++ มีฟังก์ชัน make_heap() ไวยากรณ์คือ:
แม่แบบ < ระดับ RandomAccessIterator, ระดับ เปรียบเทียบ >constexpr โมฆะ make_heap ( RandomAccessIterator ก่อน RandomAccessIterator สุดท้าย เปรียบเทียบ comp ) ;
มันใช้ตัววนซ้ำที่ชี้ไปที่องค์ประกอบแรกของเวกเตอร์เป็นอาร์กิวเมนต์แรก จากนั้นตัววนซ้ำจะชี้ไปที่ส่วนท้ายของเวกเตอร์เป็นอาร์กิวเมนต์สุดท้าย สำหรับรายการที่ไม่เรียงลำดับก่อนหน้านี้ ไวยากรณ์จะถูกใช้ดังต่อไปนี้เพื่อรับฮีปขั้นต่ำ:
เวกเตอร์ < int > vtr = { 9 , 19 , 24 , 5 , 3 , สิบเอ็ด , 14 , 22 , 7 , 6 , 17 , สิบห้า } ;เวกเตอร์ < int > :: iterator iterB = วีทีอาร์ เริ่ม ( ) ;
เวกเตอร์ < int > :: iterator iterE = วีทีอาร์ จบ ( ) ;
make_heap ( iterB, iterE, มากกว่า < int > ( ) ) ;
รหัสนี้เปลี่ยนเนื้อหาเวกเตอร์เป็นการกำหนดค่าฮีปขั้นต่ำ ในเวกเตอร์ C++ ต่อไปนี้ จะใช้เวกเตอร์สองตัวแทนสองอาร์เรย์
ในการคัดลอกและส่งคืนองค์ประกอบแรกของเวกเตอร์ ให้ใช้ไวยากรณ์เวกเตอร์:
constexpr หน้าอ้างอิง ( ) ;หากต้องการลบองค์ประกอบแรกของเวกเตอร์แล้วทิ้ง ให้ใช้ไวยากรณ์เวกเตอร์:
constexpr iterator ลบ ( ตำแหน่ง const_iterator )ในการเพิ่มองค์ประกอบที่ด้านหลังของเวกเตอร์ (องค์ประกอบถัดไป) ให้ใช้ไวยากรณ์เวกเตอร์:
constexpr โมฆะ push_back ( const ตู่ & x ) ;จุดเริ่มต้นของโปรแกรมคือ:
#include#include <อัลกอริทึม>
#include <เวกเตอร์>
โดยใช้ เนมสเปซ มาตรฐาน ;
รวมอัลกอริทึมและไลบรารีเวกเตอร์ ถัดไปในโปรแกรมคือฟังก์ชัน heapsort() ซึ่งก็คือ:
โมฆะ heapsort ( เวกเตอร์ < int > & oldV, vector < int > & ใหม่V ) {ถ้า ( เก่าV. ขนาด ( ) > 0 ) {
เวกเตอร์ < int > :: iterator iterB = เก่าV. เริ่ม ( ) ;
เวกเตอร์ < int > :: iterator iterE = เก่าV. จบ ( ) ;
make_heap ( iterB, iterE, มากกว่า < int > ( ) ) ;
int ต่อไป = เก่าV. ด้านหน้า ( ) ;
เก่าV. ลบ ( iterB ) ;
ใหม่V. push_back ( ต่อไป ) ;
heapsort ( เก่าV,ใหม่V ) ;
}
}
เป็นฟังก์ชันแบบเรียกซ้ำ ใช้ฟังก์ชัน make_heap() ของไลบรารีอัลกอริทึม C++ ส่วนโค้ดที่สองในการกำหนดฟังก์ชันจะแยกองค์ประกอบแรกออกจากเวกเตอร์เก่าหลังการสร้างฮีปและเพิ่มเป็นองค์ประกอบถัดไปสำหรับเวกเตอร์ใหม่ โปรดทราบว่าในนิยามฟังก์ชัน พารามิเตอร์เวกเตอร์เป็นข้อมูลอ้างอิง ในขณะที่ฟังก์ชันถูกเรียกด้วยตัวระบุ (ชื่อ)
ฟังก์ชั่นหลัก C ++ ที่เหมาะสมสำหรับสิ่งนี้คือ:
int หลัก ( int อาร์จีซี, char ** argv ){
เวกเตอร์ < int > เก่าV = { 9 , 19 , 24 , 5 , 3 , สิบเอ็ด , 14 , 22 , 7 , 6 , 17 , สิบห้า } ;
เวกเตอร์ < int > ใหม่V ;
heapsort ( เก่าV,ใหม่V ) ;
สำหรับ ( int ผม = 0 ; ผม < ใหม่V. ขนาด ( ) ; ผม ++ ) {
ศาล << ใหม่V [ ผม ] << ' ' ;
}
ศาล << endl ;
กลับ 0 ;
}
ผลลัพธ์คือ:
3 5 6 7 9 สิบเอ็ด 14 สิบห้า 17 19 22 24เรียง (สมบูรณ์).
บทสรุป
บทความกล่าวถึงรายละเอียดลักษณะและหน้าที่ของ Heap Sort ที่รู้จักกันทั่วไปในชื่อ Heapsort ซึ่งเป็นอัลกอริธึมการเรียงลำดับ ตัวอย่าง Heapify Time Complexity, Heapsort illustration และ Heapsort เป็นอัลกอริธึมครอบคลุมและรองรับโดยตัวอย่าง ความซับซ้อนของเวลาเฉลี่ยสำหรับโปรแกรม heapsort ที่เขียนได้ดีคือ O(nlog(n))