การเรียงลำดับฮีป หมายถึงอัลกอริทึมการเรียงลำดับที่ออกแบบมาโดยใช้โครงสร้างข้อมูลฮีป การสแต็กเป็นโครงสร้างที่มีต้นไม้ไบนารีประมาณอย่างสมบูรณ์และเป็นไปตามคุณสมบัติของการซ้อน: นั่นคือค่าคีย์หรือดัชนีของโหนดเด็กนั้นมีขนาดเล็กกว่า (หรือมากกว่า) โหนดแม่
ความซับซ้อนของเวลาเฉลี่ยของการเรียงลำดับฮีปคือ (nlogn)
ขั้นตอนอัลกอริทึม:
1. สร้างกอง H [0..N-1]
2. สลับหัวฮีป (สูงสุด) และหางฮีป
3. ลดขนาดฮีปลง 1 และโทร shift_down (0) วัตถุประสงค์คือเพื่อปรับข้อมูลด้านบนของอาร์เรย์ใหม่ให้เป็นตำแหน่งที่สอดคล้องกัน
4. ทำซ้ำขั้นตอนที่ 2 จนกระทั่งขนาดของกองคือ 1
กอง:
ฮีปเป็นต้นไม้ไบนารีที่สมบูรณ์และโหนดที่ไม่ใช่ใบใด ๆ ของโหนดที่ไม่ใช่ใบของมันเป็นไปตามคุณสมบัติของมัน: key [i] <= key [2i+1] && key [i] <= key [2i+2] หรือ key [i]> = key [2i+1] && key> = key [2i+2] กองแบ่งออกเป็นกองบนขนาดใหญ่และกองด้านบนเล็ก ๆ คีย์ที่น่าพอใจ [i]> = key [2i+1] && key> = key [2i+2] เรียกว่ากองด้านบนขนาดใหญ่ คีย์ที่น่าพอใจ [i] <= key [2i+1] && key [i] <= key [2i+2] เรียกว่ากองด้านบนขนาดเล็ก จากคุณสมบัติข้างต้นเราจะเห็นได้ว่าคำหลักที่อยู่ด้านบนของกองบนขนาดใหญ่นั้นเป็นคำหลักที่ใหญ่ที่สุดและคำหลักที่อยู่ด้านบนของกองเล็ก ๆ นั้นเล็กที่สุดของคำหลักทั้งหมด
แนวคิดการเรียงลำดับของกอง:
คุณลักษณะของคำหลักที่ใหญ่ที่สุด (คำหลักขั้นต่ำ) ที่บันทึกไว้ที่ด้านบนของฮีปด้านบนขนาดใหญ่ (กองด้านบนขนาดเล็ก) ทำให้ง่ายต่อการเลือกบันทึกที่ใหญ่ที่สุด (บันทึกขั้นต่ำ) จากความผิดปกติในแต่ละครั้ง แนวคิดพื้นฐานคือ (กองใหญ่สุด): 1) สร้างลำดับเริ่มต้นของคำหลักที่จะเรียงลำดับ (R1, R2 … .rn) ลงในกองบนขนาดใหญ่ซึ่งเป็นพื้นที่เริ่มต้นที่ไม่เป็นระเบียบ; 2) แลกเปลี่ยนองค์ประกอบด้านบนของฮีป R [1] กับองค์ประกอบสุดท้าย R [n] จากนั้นได้รับพื้นที่ที่ไม่เป็นระเบียบใหม่ (R1, R2, … RN-1) และภูมิภาคที่สั่งใหม่ (RN) และตอบสนอง R [1,2 … N-1] <= R [n]; 3) ตั้งแต่กองใหม่ R [1] หลังจากการแลกเปลี่ยนอาจละเมิดคุณสมบัติของกองจึงจำเป็นต้องปรับพื้นที่ที่ไม่เป็นระเบียบในปัจจุบัน (R1, R2, … RN-1) เป็นกองใหม่แล้วแลกเปลี่ยน r [1] กับองค์ประกอบสุดท้ายของพื้นที่ที่ไม่เป็นระเบียบอีกครั้ง ทำซ้ำกระบวนการนี้จนกว่าจำนวนองค์ประกอบในพื้นที่ที่สั่งซื้อคือ N-1 และกระบวนการเรียงลำดับทั้งหมดเสร็จสิ้น กระบวนการดำเนินการมีดังนี้: 1) เริ่มต้นกอง: สร้าง r [1..N] เป็นกอง; 2) แลกเปลี่ยนองค์ประกอบด้านบนของฮีป R [1] ของพื้นที่ที่ไม่ได้เรียงลำดับปัจจุบันด้วยบันทึกสุดท้ายในช่วงเวลาจากนั้นปรับพื้นที่ที่ไม่ได้เรียงลำดับใหม่เป็นกองใหม่ ดังนั้นสำหรับการเรียงลำดับฮีปการดำเนินการที่สำคัญที่สุดทั้งสองคือการสร้างกองเริ่มต้นและปรับกอง ในความเป็นจริงการสร้างกองเริ่มต้นเป็นกระบวนการของการปรับฮีป แต่การสร้างกองเริ่มต้นคือการปรับโหนดที่ไม่ใช่ใบทั้งหมด
ตัวอย่างของภาพประกอบ
ได้รับอาร์เรย์รูปร่าง A [] = {16,7,3,20,17,8}, heap จัดเรียงมัน ขั้นแรกให้สร้างต้นไม้ไบนารีที่สมบูรณ์ตามองค์ประกอบอาร์เรย์และรับ
จากนั้นคุณต้องสร้างกองเริ่มต้นแล้วเริ่มการปรับจากโหนดที่ไม่ใช่ใบล่าสุด กระบวนการปรับมีดังนี้:
หลังจากการแลกเปลี่ยน 20 และ 16, 16 ทำให้ 16 ไม่ตรงตามคุณสมบัติของกองดังนั้นจึงต้องมีการปรับใหม่
สิ่งนี้ให้กองเริ่มต้น
เมื่อมีการปรับก่อนมันจะกลายเป็นกองบนใหญ่
นั่นคือการปรับแต่ละครั้งคือการเลือกโหนดที่ใหญ่ที่สุดจากโหนดพาเรนต์โหนดเด็กซ้ายและโหนดลูกที่ถูกต้องในการแลกเปลี่ยนกับโหนดพาเรนต์ (หลังจากการแลกเปลี่ยนโหนดเด็กที่ถูกแลกเปลี่ยนอาจทำให้โหนดเด็กถูกแลกเปลี่ยนเพื่อไม่ให้ตรงตามธรรมชาติของกอง ด้วยกองเริ่มต้นคุณสามารถเรียงลำดับได้
ในเวลานี้ 3 ตั้งอยู่ที่ด้านบนของกองและคุณสมบัติไม่เต็มไปด้วยกอง คุณต้องปรับและปรับต่อไป
ด้วยวิธีนี้ช่วงเวลาทั้งหมดมีระเบียบอยู่แล้ว จากกระบวนการข้างต้นเราจะเห็นได้ว่าการเรียงลำดับของกองเป็นตัวเลือกการเรียงลำดับการเรียงลำดับการเลือกต้นไม้ แต่เพื่อที่จะเลือกคำสั่งซื้อโดยตรงเพื่อเลือกบันทึกสูงสุดจาก R [1 ... n] ต้องเปรียบเทียบ N-1 ครั้งจากนั้นเลือกบันทึกสูงสุดจาก R [1 ... N-2] ต้องเปรียบเทียบ N-2 ครั้ง ในความเป็นจริงการเปรียบเทียบ N-2 เหล่านี้จำนวนมากได้ทำในการเปรียบเทียบ N-1 ก่อนหน้านี้และการเรียงลำดับการเลือกต้นไม้เพียงแค่ใช้ลักษณะของต้นไม้เพื่อบันทึกผลการเปรียบเทียบก่อนหน้านี้ดังนั้นจำนวนการเปรียบเทียบสามารถลดลงได้ สำหรับลำดับคำหลัก n ที่แย่ที่สุดแต่ละโหนดจะต้องเปรียบเทียบ log2 (n) ครั้งดังนั้นความซับซ้อนของเวลากรณีที่เลวร้ายที่สุดคือ nlogn การเรียงลำดับฮีปไม่เสถียรและไม่เหมาะสำหรับการเรียงลำดับที่มีระเบียนน้อยลง มีการอธิบายมากมายข้างต้น ในระยะสั้นการปฏิบัติขั้นพื้นฐานของการเรียงลำดับฮีปคือ: ก่อนอื่นให้ใช้ข้อมูลต้นฉบับเพื่อสร้างกองขนาดใหญ่ (เล็ก) เป็นพื้นที่ที่ไม่มีการเรียงลำดับเดิมและจากนั้นทุกครั้งที่องค์ประกอบด้านบนของกองถูกนำออกและวางไว้ในพื้นที่สั่งซื้อ เนื่องจากองค์ประกอบด้านบนของกองถูกนำออกมาเราจึงวางองค์ประกอบสุดท้ายไว้ในกองไว้ที่ด้านบนของกองดังนั้นคุณสมบัติของกองจะถูกทำลาย เราจำเป็นต้องปรับกองอีกครั้งและดำเนินการต่อ N จากนั้นองค์ประกอบ n ในพื้นที่ที่ไม่มีการเรียงลำดับจะถูกใส่เข้าไปในพื้นที่ที่สั่งซื้อและกระบวนการเรียงลำดับเสร็จสิ้น
(การสร้างสแต็คมาจากล่างขึ้นไปด้านบน)
การใช้งานจริง:
ในทางปฏิบัติเราทำการเรียงลำดับกองเพื่อให้ได้ค่าสูงสุดหรือต่ำสุดภายใต้เงื่อนไขบางประการ ตัวอย่างเช่น: 10 ค่าสูงสุดจะต้องพบใน 100 ตัวเลข ดังนั้นเราจึงกำหนดกองขนาด 10 สร้างสิบข้อมูลแรกใน 100 เป็นกองเล็ก ๆ (ด้านบนของกอง) จากนั้นเปรียบเทียบกับส่วนบนของกองจากข้อมูลที่ 11 ใน 100 ข้อมูล หากด้านบนของฮีปมีขนาดเล็กกว่าข้อมูลปัจจุบันส่วนบนของฮีปจะโผล่ขึ้นมากดข้อมูลปัจจุบันไปที่ด้านบนของฮีปจากนั้นย้ายข้อมูลจากด้านบนของกองไปยังตำแหน่งที่แน่นอน
รหัส:
ระดับสาธารณะ test0 {int คงที่ [] arr; // array heap, array ที่ถูกต้อง public test0 (int m) {arr = new int [m];} int คงที่ m = 0; ขนาด int คงที่ = 0; // ใช้เพื่อทำเครื่องหมายข้อมูลที่ถูกต้อง {16,4,5,9,1,10,11,12,13,14,15,2,3,6,7,8,111,222,333,555,66,67,54}; // ขนาดกองคือ 10 // arr = ใหม่ int [10]; ถ้า (ขนาด <arr.length) {arr [size] = v; add_sort (ขนาด); // add_sort1 (ขนาด); ขนาด ++;} อื่น {arr [0] = v; add_sort1 (0);}} printsmall printsmall (int i = 0; Void del () {size-; arr [0] = arr [9]; add_sort1 (0);} โมฆะสาธารณะขนาดเล็ก (ดัชนี int) {ถ้า (m <arr.length) {add_sort (ดัชนี); m ++;} อื่น {add_sort1 (ดัชนี); m ++; พิกัด: ดัชนี *โหนดลูกซ้าย: ดัชนี *2 *โหนดลูกขวา: ดัชนี *2+1 *ถ้าโหนดสุดท้ายในอาร์เรย์เป็นคี่มันเป็นลูกซ้าย *ถ้าคนสุดท้ายในอาร์เรย์เป็นลูกที่เหมาะสมถ้าโหนดเด็กมีขนาดใหญ่กว่าโหนดพาเรนต์ หากเด็กที่เหมาะสมมีขนาดใหญ่กว่าเด็กซ้ายการแลกเปลี่ยนค่าจะถูกดำเนินการ**/int par; ถ้า (ดัชนี! = 0) {ถ้า (ดัชนี%2 == 0) {par = (index-1)/2; ถ้า (arr [arr] <arr [par]) {swap (arr, aldand, par); add_sort (par) dex] <arr [par]) {swap (arr, index, par);} add_sort (par);}} else {par = index/2; ถ้า (arr [arr [arr [arr [arr [par]) {swap (arr, ดัชนี, par); add_sort (par); พาร์*2+1); ถ้า (arr [arr [arr] <arr [par]) {swap (arr, index, par);} add_sort (par);}}}} โมฆะสาธารณะ add_sort1 (ดัชนี int) {// ปรับ heap ขนาดเล็ก/*ปรับด้านบน*2 max = 0; ถ้า (ซ้าย <10 && arr [ซ้าย] <arr [index]) {max = ซ้าย;} else {max = index;} ถ้า (ขวา <10 && arr [ขวา] <arr [max]) {max = ขวา;} if (max! = index) นำเข้า java.util.scanner; คลาสสาธารณะ main_test0 {โมฆะคงที่สาธารณะหลัก (สตริง args []) {สแกนสแกนเนอร์ = สแกนเนอร์ใหม่ (System.in); System.out.println ("(กองเล็ก ๆ ) {16,4,5,9,1,10,11,12,13,14,15,2,3,6,7,8}; สำหรับ (int i = 0; i <a.length; i ++) {test.addtosmall (a [i]);} test.printsmall (test.del ();ตัวอย่างการเรียงลำดับของ Java Heap ด้านบน (กองท็อปบิ๊ก, กองเล็ก ๆ ) เป็นเนื้อหาทั้งหมดที่ฉันแบ่งปันกับคุณ ฉันหวังว่าคุณจะให้ข้อมูลอ้างอิงและฉันหวังว่าคุณจะสนับสนุน wulin.com มากขึ้น