โปรแกรมเมอร์สามารถดึงองค์ประกอบสูงสุดได้อย่างง่ายดายโดยใช้ ' กองสูงสุด ” ต้นไม้ไบนารี เช่นเดียวกับในทรีนี้ องค์ประกอบสูงสุดจะอยู่ที่โหนดบนสุดของทรีเสมอ ซึ่งเรียกว่า “ ราก ” โหนด นอกจากนี้ยังมีการแทรกและลบองค์ประกอบที่มีประสิทธิภาพในขณะที่รักษาลำดับการจัดเรียง นอกจากนี้ “Max Heap” สามารถทำงานตามกำหนดเวลาได้อย่างง่ายดายโดยอิงจากลำดับความสำคัญหรือเกณฑ์อื่นๆ
บทความนี้จะอธิบายเนื้อหาต่อไปนี้:
วิธีใช้ Max Heap ใน Java
เอ “ กองสูงสุด ” ถูกใช้เป็นโครงสร้างข้อมูลพื้นฐานสำหรับการนำคิวลำดับความสำคัญไปใช้ ในคิวลำดับความสำคัญ ข้อมูลจะถูกประมวลผลตามค่าลำดับความสำคัญที่กำหนด นอกจากนี้ยังสามารถใช้เพื่อจัดเรียงองค์ประกอบข้อมูลตามลำดับจากมากไปน้อยได้อย่างมีประสิทธิภาพ
สามารถสร้าง 'Max Heap' ได้โดยใช้สองวิธีที่อธิบายไว้ในตัวอย่างตัวแปลงสัญญาณด้านล่าง:
วิธีที่ 1: ใช้วิธี “maxHeapify()”
“ maxHeapify() ” วิธีการสร้าง “ กองสูงสุด ” จากการรวบรวมองค์ประกอบที่มีอยู่โดยการแปลงโครงสร้างข้อมูล ยิ่งไปกว่านั้น วิธีนี้ช่วยในการปรับเปลี่ยนอาร์เรย์เดิมเพื่อลดความต้องการหน่วยความจำเพิ่มเติม
ตัวอย่างเช่น ไปที่โค้ดด้านล่างเพื่อสร้าง “ กองสูงสุด ” โดยใช้วิธี “maxHeapify()”:
นำเข้า java.util.ArrayList;นำเข้า java.util.Collections;
นำเข้า java.util.List;
MaxHeapifyExam คลาสสาธารณะ {
โมฆะสาธารณะคงหลัก ( สตริง [ ] หาเรื่อง ) // การสร้างหลัก ( ) วิธี
{
รายการ < จำนวนเต็ม > การทดสอบ Ele = ArrayList ใหม่ <> ( ) ;
ทดสอบ Ele.add ( 5 ) ;
ทดสอบ Ele.add ( 3 ) ;
ทดสอบ Ele.add ( 8 ) ;
ทดสอบ Ele.add ( 2 ) ;
ทดสอบ Ele.add ( 1 ) ;
ทดสอบ Ele.add ( 7 ) ;
System.out.println ( 'รายการต้นฉบับ: ' + การทดสอบ ) ;
maxHeapify ( การทดสอบ ) ;
System.out.println ( 'กองสูงสุดที่สร้างขึ้น: ' + การทดสอบ ) ;
}
โมฆะคงที่ส่วนตัว maxHeapify ( รายการ < จำนวนเต็ม > การทดสอบ ) {
int k = testEle.size ( ) ;
สำหรับ ( int ผม = k / 2 - 1 ; ฉัน > = 0 ; ฉัน-- ) {
กอง ( การทดสอบEle, k, i ) ;
}
}
โมฆะส่วนตัวคง heapify ( รายการ < จำนวนเต็ม > การทดสอบEle, int k, int i ) {
int มากกว่า = i;
int leftSide = 2 * ฉัน + 1 ;
int rightSide = 2 * ฉัน + 2 ;
ถ้า ( ด้านซ้าย < เค && ทดสอบ Ele.get ( ด้านซ้าย ) > ทดสอบ Ele.get ( มากขึ้น ) ) {
มากกว่า = leftSide;
}
ถ้า ( ด้านขวา < เค && ทดสอบ Ele.get ( ด้านขวา ) > ทดสอบ Ele.get ( มากขึ้น ) ) {
มากกว่า = rightSide;
}
ถ้า ( มากขึ้น ! = ฉัน ) {
Collections.swap ( การทดสอบEle, i, มากกว่า ) ;
กอง ( การทดสอบEle, k, มากกว่า ) ;
}
}
}
คำอธิบายของรหัสด้านบน:
- อันดับแรก รายการ “ การทดสอบ ” เริ่มต้นด้วยองค์ประกอบข้อมูลจำลองใน “ หลัก() วิธีการ” และพิมพ์บนคอนโซล
- ถัดไป รายการ 'testEle' จะถูกส่งผ่านไปยังฟังก์ชัน 'maxHeapify()' จากนั้นรายการที่ส่งคืนจะแสดงบนคอนโซล
- จากนั้น “ maxHeapify() ” วิธีการเริ่มต้นและดึงขนาดของรายการที่ให้มาโดยใช้ “ ขนาด() ' วิธี.
- ถัดไป ใช้ “ สำหรับ ” วนซ้ำเพื่อตั้งค่าโครงสร้างฮีปและคำนวณตำแหน่งของแต่ละโหนด
- ตอนนี้ใช้ ' กอง () ” วิธีการและตั้งค่าตำแหน่งสำหรับโหนด 'ด้านบน' 'ซ้าย' และ 'ขวา' โดยกำหนดค่าให้กับตัวแปร 'มากกว่า' 'ด้านซ้าย' และ 'ด้านขวา' ตามลำดับ
- หลังจากนั้นให้ใช้หลาย ๆ “ ถ้า ” ข้อความเงื่อนไขเพื่อตรวจสอบว่า “ ด้านซ้าย ” โหนดมีขนาดใหญ่กว่า “ ด้านขวา ” โหนดและในทางกลับกัน ในท้ายที่สุด ค่าที่มากกว่าจะถูกเก็บไว้ใน “ มากขึ้น ” โหนด
- ในที่สุด ใหม่ “ มากขึ้น ” ค่าโหนดถูกตรวจสอบด้วยค่าที่เก็บไว้แล้วใน “ มากขึ้น ” ตัวแปรโหนด และ ' แลกเปลี่ยน() ” ฟังก์ชันทำงานตามการตั้งค่าที่ใหญ่ที่สุดใน “ มากขึ้น ' ตัวแปร.
หลังจากสิ้นสุดขั้นตอนการดำเนินการ:
ภาพรวมแสดงฮีปสูงสุดที่สร้างขึ้นโดยใช้ ' maxHeapify() วิธีการ” ใน Java
วิธีที่ 2: ใช้เมธอด “Collections.reverseOrder()”
“ Collections.reverseOrder() ” วิธีการนำเสนอวิธีการที่ง่ายและรัดกุมในการสร้าง “ กองสูงสุด ” โดยเรียงลำดับคอลเลกชันในลำดับย้อนกลับ สิ่งนี้ทำให้โค้ดสามารถใช้ซ้ำได้และหลีกเลี่ยงความจำเป็นในการใช้แบบกำหนดเอง “ กอง ” ตรรกะตามที่แสดงในข้อมูลโค้ดด้านล่าง:
นำเข้า java.util.ArrayList;นำเข้า java.util.Collections;
นำเข้า java.util.List;
ReverseOrderExample คลาสสาธารณะ {
โมฆะสาธารณะคงหลัก ( สตริง [ ] หาเรื่อง ) // การสร้างหลัก ( ) วิธี
{
รายการ < จำนวนเต็ม > การทดสอบ Ele = ArrayList ใหม่ <> ( ) ;
ทดสอบ Ele.add ( 5 ) ;
ทดสอบ Ele.add ( 38 ) ;
ทดสอบ Ele.add ( 98 ) ;
ทดสอบ Ele.add ( 26 ) ;
ทดสอบ Ele.add ( 1 ) ;
ทดสอบ Ele.add ( 73 ) ;
System.out.println ( 'รายการต้นฉบับ: ' + การทดสอบ ) ;
Collections.sort ( การทดสอบ Ele, Collections.reverseOrder ( ) ) ;
System.out.println ( 'กองสูงสุดที่สร้างขึ้น: ' + การทดสอบ ) ;
}
}
คำอธิบายของรหัสด้านบน:
- ขั้นแรกให้นำเข้า ' รายการอาร์เรย์ ”, “ คอลเลกชัน ' และ ' รายการ ” ยูทิลิตี้ในไฟล์ Java
- จากนั้นสร้าง “ รายการ ” ชื่อว่า “ การทดสอบ ” และแทรกองค์ประกอบจำลองในรายการ
- ต่อไป “ เรียงลำดับ() วิธีการ ” ใช้เพื่อจัดเรียงองค์ประกอบข้อมูลในลำดับจากน้อยไปมากและส่งรายการเป็นพารามิเตอร์ตาม “ Collections.reverseOrder() ' วิธี. สิ่งนี้ทำให้การเรียงลำดับของ“ การทดสอบ ” รายการในลำดับย้อนกลับ
หลังจากสิ้นสุดขั้นตอนการดำเนินการ:
ภาพรวมแสดงให้เห็นว่า 'Max Heap' ถูกสร้างขึ้นและจัดเรียงโดยใช้เมธอด 'Collections.reverseOrder()'
บทสรุป
ด้วยการสร้าง “ กองสูงสุด ” ผู้ใช้สามารถใช้เมธอด “maxHeapify()” และ “Collections.reverseOrder()” พวกเขาจัดการคอลเลกชันขององค์ประกอบในลักษณะที่ช่วยให้เข้าถึงองค์ประกอบสูงสุดได้อย่างรวดเร็วและบำรุงรักษาลำดับการจัดเรียงอย่างมีประสิทธิภาพ ขึ้นอยู่กับข้อกำหนดเฉพาะและระดับการควบคุมที่จำเป็นในกระบวนการสร้างฮีปเท่านั้น