ฮีปเป็นโครงสร้างที่สำคัญในโครงสร้างข้อมูล หลังจากทำความเข้าใจแนวคิดและการดำเนินงานของ "heap" คุณสามารถควบคุมการเรียงลำดับของกองได้อย่างรวดเร็ว
แนวคิดของกอง
HEAP เป็นต้นไม้ไบนารีที่สมบูรณ์แบบพิเศษ หากค่าของโหนดทั้งหมดของต้นไม้ไบนารีที่สมบูรณ์นั้นไม่เล็กกว่าลูกของพวกเขามันจะเรียกว่ากองรากขนาดใหญ่ (หรือกองบนสุด); หากค่าของโหนดทั้งหมดไม่ใหญ่กว่าลูกของพวกเขามันจะเรียกว่ากองรากขนาดเล็ก (หรือกองเล็ก ๆ ด้านบน)
ในอาร์เรย์ (การจัดเก็บโหนดรูทในหมายเลขตัวห้อย 0) มันเป็นเรื่องง่ายที่จะได้รับสมการต่อไปนี้ (สมการทั้งสองนี้มีความสำคัญมาก):
1. โหนดที่มีตัวห้อยคือ i และพิกัดของโหนดพาเรนต์คือ (I-1)/2;
2. โหนดที่มีตัวห้อยคือ i, พิกัดของโหนดลูกซ้ายคือ 2*i+1 และโหนดลูกที่ถูกต้องคือ 2*i+2
สถานประกอบการและการบำรุงรักษากอง
กองสามารถรองรับการดำเนินการหลายอย่าง แต่ตอนนี้เราสนใจเพียงสองประเด็นเท่านั้น:
1. ได้รับอาร์เรย์ที่ไม่ได้เรียงลำดับวิธีการสร้างเป็นกอง?
2. หลังจากลบองค์ประกอบด้านบนของกองแล้ววิธีปรับแต่งองค์ประกอบเป็นกองใหม่?
มาดูคำถามที่สองก่อน สมมติว่าเรามีกองรากขนาดใหญ่สำเร็จรูปแล้ว ตอนนี้เราลบองค์ประกอบรูท แต่เราไม่ย้ายองค์ประกอบอื่น ๆ คิดเกี่ยวกับสิ่งที่เกิดขึ้น: องค์ประกอบรูทว่างเปล่า แต่องค์ประกอบอื่น ๆ ยังคงรักษาคุณสมบัติของกอง เราสามารถย้ายองค์ประกอบสุดท้าย (ชื่อรหัส a) ไปยังตำแหน่งขององค์ประกอบรูท หากไม่ใช่กรณีพิเศษคุณสมบัติของกองจะถูกทำลาย แต่นี่เป็นเพราะ A มีขนาดเล็กกว่าองค์ประกอบลูกหนึ่ง ดังนั้นเราสามารถสลับ A และองค์ประกอบลูกนี้เป็นตำแหน่ง หาก A มากกว่าองค์ประกอบของเด็กทั้งหมดจะมีการปรับกอง มิฉะนั้นให้ทำซ้ำกระบวนการข้างต้นองค์ประกอบ A ยังคง "จม" ในโครงสร้างต้นไม้จนกว่าจะเหมาะสมและอาร์เรย์จะคืนคุณสมบัติของกอง กระบวนการข้างต้นโดยทั่วไปเรียกว่า "การคัดกรอง" และทิศทางเห็นได้ชัดจากบนลงล่าง
สิ่งนี้เป็นจริงเมื่อลบองค์ประกอบและการแทรกองค์ประกอบใหม่ ความแตกต่างคือเราใส่องค์ประกอบใหม่ในตอนท้ายแล้วเปรียบเทียบกับโหนดพาเรนต์นั่นคือกรองจากล่างขึ้นบน
ดังนั้นวิธีแก้ปัญหาแรก?
หนังสือหลายเล่มเกี่ยวกับโครงสร้างข้อมูลที่ฉันอ่านกำลังกรองจากโหนดที่ไม่ใช่ใบแรกจนกว่าองค์ประกอบรูทจะถูกกรอง วิธีนี้เรียกว่า "วิธีการกรอง" ซึ่งต้องใช้องค์ประกอบการกรองลูป N/2
แต่เรายังสามารถเรียนรู้จากความคิดของ "การสร้างบางสิ่งบางอย่างโดยไม่มีอะไร" เราสามารถมองว่าองค์ประกอบแรกเป็นกองและจากนั้นเพิ่มองค์ประกอบใหม่อย่างต่อเนื่อง วิธีนี้เรียกว่า "วิธีการแทรก" ซึ่งต้องใช้การแทรกลูปขององค์ประกอบ (N-1)
เนื่องจากวิธีการกรองและวิธีการแทรกแตกต่างกัน heaps ที่พวกเขาสร้างโดยทั่วไปจะแตกต่างกันสำหรับข้อมูลเดียวกัน
หลังจากความเข้าใจอย่างคร่าวๆเกี่ยวกับกองการเรียงลำดับกองเป็นสิ่งที่เป็นธรรมชาติ
ภาพรวมอัลกอริทึม/แนวคิด
เราต้องการลำดับจากน้อยไปมากเราควรทำอย่างไร? เราสามารถสร้างฮีปขั้นต่ำจากนั้นส่งออกองค์ประกอบรูทในแต่ละครั้ง อย่างไรก็ตามวิธีนี้ต้องใช้พื้นที่เพิ่มเติม (มิฉะนั้นจะทำให้เกิดการเคลื่อนไหวขององค์ประกอบจำนวนมากและความซับซ้อนของมันจะเพิ่มขึ้นเป็น o (n^2)) ถ้าเราต้องการการเรียงลำดับในสถานที่ (เช่นไม่อนุญาตให้มีความซับซ้อนของอวกาศ O (n))?
มีวิธี เราสามารถสร้างฮีปสูงสุดจากนั้นเราจะส่งออกค่าสูงสุดในตำแหน่งสุดท้ายและค่าสูงสุดที่สองในตำแหน่งสุดท้าย ... เนื่องจากองค์ประกอบสูงสุดออกมาในแต่ละครั้งจะเพิ่มพื้นที่ว่างแรกเราจึงสามารถวางองค์ประกอบดังกล่าวได้โดยไม่ต้องใช้พื้นที่เพิ่มเติม ความคิดที่สวยงามมากใช่มั้ย
Public Class Heapsort {โมฆะคงที่สาธารณะหลัก (String [] args) {int [] arr = {50, 10, 90, 30, 70, 40, 80, 60, 20}; System.out.println ("ก่อนการเรียงลำดับ:"); สำหรับ (int i = 0; i <arr.length; i ++) {system.out.print (arr [i]+""); } // Heap Sorting Heapsort (arr); System.out.println (); System.out.println ("หลังจากการเรียงลำดับ:"); สำหรับ (int i = 0; i <arr.length; i ++) {system.out.print (arr [i]+""); }} / *** HEAP เรียงลำดับ* / Void heapsort (int [] arr) {// สร้างลำดับที่จะจัดเรียงเป็นกองขนาดใหญ่สำหรับ (int i = arr.length / 2; i> = 0; i-) {heapadjust (arr, i, arr.length); } // ค่อยๆเปลี่ยนโหนดรูทของค่าสูงสุดแต่ละค่าด้วยองค์ประกอบสิ้นสุดและปรับทรีไบนารีเพื่อให้เป็นกองบนขนาดใหญ่สำหรับ (int i = arr.length-1; i> 0; i--) {swap (arr, 0, i); // แลกเปลี่ยนสถิติสูงสุดของฮีปด้วยบันทึกล่าสุดของ Heapadjust ที่ไม่ได้เรียงลำดับในปัจจุบัน (arr, 0, i); // หลังจากการแลกเปลี่ยนมีความจำเป็นที่จะต้องตรวจสอบอีกครั้งว่ากองตรงกับกองใหญ่ หากไม่ตรงตามนั้นจะต้องมีการปรับ}} / *** กระบวนการสร้างฮีป* @param arr อาร์เรย์ที่ต้องจัดเรียง* @param i จำนวนของโหนดรูทของกองที่ต้องสร้าง* @param n ความยาวของอาร์เรย์* / โมฆะ พ่อใน; สำหรับ (พ่อ = arr [i]; leftchild (i) <n; i = เด็ก) {child = leftchild (i); // ถ้าทรีย่อยด้านซ้ายมีขนาดเล็กกว่าทรีย่อยด้านขวาคุณจะต้องเปรียบเทียบทรีย่อยด้านขวากับโหนดแม่ถ้า (เด็ก! = n - 1 && arr [ลูก] <arr [เด็ก+1]) {เด็ก ++; // เพิ่มหมายเลขซีเรียลโดย 1 ชี้ไปที่ทรีย่อยด้านขวา} // ถ้าโหนดแม่มีขนาดเล็กกว่าโหนดลูกคุณต้องแลกเปลี่ยนถ้า (พ่อ <arr [เด็ก]) {arr [i] = arr [child]; } else {break; // โครงสร้างกองบนขนาดใหญ่ไม่ได้ถูกทำลายไม่จำเป็นต้องมีการปรับ}} arr [i] = พ่อ; } // รับโหนดเด็กซ้ายส่วนตัวคงที่ int ซ้าย (int i) {return 2 * i + 1; } // swap องค์ประกอบตำแหน่งโมฆะคงแบบคงที่ส่วนตัว (int [] arr, int index1, int index2) {int tmp = arr [arred1]; arr [index1] = arr [index2]; arr [index2] = tmp; -