ทำความเข้าใจเกี่ยวกับการใช้งาน Binary Heap ใน Java

บทความนี้จะให้ภาพรวมที่สมบูรณ์เกี่ยวกับการทำงานของการจัดเรียงฮีปและในภายหลังเราจะเรียนรู้การใช้งาน Binary Heap ใน Java

ออกจากโปรแกรมใน java

นี่คือวาระการประชุมสำหรับบทความนี้:

1. Heap Sort คืออะไร?
2. Max Heap
3. มินฮีป
4. การใช้งาน Heap ใน Java
   • แผนภาพ
   • รหัส

เอาล่ะ!

Heap Sort คืออะไร?

Heap เป็นโครงสร้างข้อมูลแบบต้นไม้ มันมีโหนด โหนดประกอบด้วยองค์ประกอบบางอย่าง ทุกโหนดมีองค์ประกอบเดียว

โหนดอาจมีลูก ถ้าในกรณีที่ไม่มีลูกเรียกว่า Leaf

มีกฎสองข้อที่ต้องปฏิบัติตาม:

• ค่าของทุกโหนดต้องน้อยกว่าหรือเท่ากับค่าทั้งหมดที่เก็บไว้ในลูกของมัน
• มีความสูงน้อยที่สุด

ฮีปส์มีประสิทธิภาพอย่างมากในการแยกไฟล์องค์ประกอบน้อยที่สุดหรือมากที่สุด

ไปที่ min heap กันเลย!

มินฮีป

Min heap คือต้นไม้ไบนารีที่สมบูรณ์ซึ่งค่าขององค์ประกอบรูทน้อยกว่าหรือเท่ากับองค์ประกอบลูกอย่างใดอย่างหนึ่ง

การเป็นตัวแทนของฮีปขั้นต่ำ

Arr [(i-1) / 2]: สิ่งนี้จะส่งคืนโหนดหลัก

อะไรคือความแตกต่างระหว่างคลาสและอินเทอร์เฟซ

Arr [(2 * i) + 1]: สิ่งนี้จะส่งคืนโหนดลูกทางซ้าย

Arr [(2 * i) + 2]: สิ่งนี้จะส่งคืนโหนดลูกที่ถูกต้อง

มีวิธีการบางอย่างของ Min Heap:

• แทรก(): เพิ่มคีย์ใหม่ที่ส่วนท้ายของต้นไม้ ในกรณีที่คีย์ใหม่มีขนาดใหญ่กว่าพาเรนต์ก็ไม่จำเป็นต้องทำอะไรอีกเราต้องสำรวจเพื่อตั้งค่าคุณสมบัติฮีป
• getMin (): วิธีนี้ช่วยในการคืนค่าองค์ประกอบราก
• extractMin (): วิธีนี้จะคืนค่าต่ำสุดธาตุ.

ย้ายไปที่ Max heap ทันที

กองสูงสุด

Max heap คือต้นไม้ไบนารีที่สมบูรณ์ซึ่งค่าขององค์ประกอบรูทมากกว่าหรือเท่ากับองค์ประกอบลูกอย่างใดอย่างหนึ่ง

Max heap ประกอบด้วยหลายวิธีเช่นกัน!

• แทรก (): มันจะแทรกองค์ประกอบในฮีป
• ลบ() : มันจะลบองค์ประกอบออกจากฮีป
• FindMax (): มันจะค้นหาองค์ประกอบสูงสุดจากฮีป
• printHeap (): มันจะพิมพ์เนื้อหาของฮีป

ตอนนี้ให้ฉันแสดงการใช้งานฮีปผ่านไดอะแกรมและต่อมาเป็น Javaรหัส.

การใช้งาน Heap ใน Java

แผนภาพ:

วิธีตั้งค่า classpath ใน linux

แผนภาพด้านบนแสดงไบนารีฮีปใน Java ดังที่คุณได้เรียนรู้ว่ามีสองฮีป: ฮีปขั้นต่ำและฮีปสูงสุดนี่คือแผนภาพ:

ตอนนี้ไปยังส่วนถัดไปของเราเราจะดูวิธีใช้ไบนารีฮีปใน Java

รหัส:

คลาสสาธารณะ BinaryHeap {private static final int d = 2 private int [] heap private int heapSize / ** * ซึ่งจะเริ่มต้นฮีปของเราด้วยขนาดเริ่มต้น * / public BinaryHeap (int ความจุ) {heapSize = 0 heap = new int [capacity + 1] Arrays.fill (heap, -1)} / ** * สิ่งนี้จะตรวจสอบว่าฮีปว่างหรือไม่ * ความซับซ้อน: O ( 1) * / public boolean isEmpty () {return heapSize == 0} / ** * สิ่งนี้จะตรวจสอบว่าฮีปเต็มหรือไม่ * Complexity: O (1) * / public boolean isFull () {return heapSize == heap .length} private int parent (int i) {return (i-1) / d} private int kthChild (int i, int k) {return d * i + k} / ** * สิ่งนี้จะแทรกองค์ประกอบใหม่ในฮีป * ความซับซ้อน: O (log N) * ในกรณีที่เลวร้ายที่สุดเราจำเป็นต้องสำรวจจนถึงรูท * / การแทรกโมฆะสาธารณะ (int x) {if (isFull ()) โยน NoSuchElementException ใหม่ ('ฮีปเต็มไม่มีช่องว่างให้แทรก องค์ประกอบใหม่ ') heap [heapSize ++] = x heapifyUp (heapSize-1)} / ** * สิ่งนี้จะลบองค์ประกอบที่ index x * Complexity: O (log N) * * / public int delete (int x) {if (isEmpty ()) โยน NoSuchElementException ใหม่ ('Heap ว่างเปล่าไม่มีองค์ประกอบที่จะลบ') int key = heap [x] heap [x] = heap [heapSize -1] heapSize-- heapifyDown (x) retu rn key} / ** * วิธีนี้ใช้เพื่อรักษาคุณสมบัติฮีปในขณะที่ใส่องค์ประกอบ * * / private void heapifyUp (int i) {int temp = heap [i] while (i> 0 && temp> heap [parent (i)]) {heap [i] = heap [parent (i)] i = parent (i)} heap [i] = temp} / ** * วิธีนี้ใช้เพื่อรักษาคุณสมบัติฮีปไว้ในขณะที่ลบองค์ประกอบ * * / heapifyDown โมฆะส่วนตัว (int i) {int child int temp = heap [i] ในขณะที่ (kthChild (i, 1)heap [rightChild]? leftChild: rightChild} / ** * วิธีนี้ใช้เพื่อพิมพ์องค์ประกอบทั้งหมดของ heap * * / public void printHeap () {System.out.print ('nHeap =') สำหรับ (int i = 0 i
ด้วยเหตุนี้เราจึงมาถึงจุดสิ้นสุดของบทความนี้เกี่ยวกับ Binary Heap ใน Java ตรวจสอบไฟล์    โดย Edureka บริษัท การเรียนรู้ออนไลน์ที่เชื่อถือได้ซึ่งมีเครือข่ายผู้เรียนที่พึงพอใจมากกว่า 250,000 คนกระจายอยู่ทั่วโลก หลักสูตรการฝึกอบรมและการรับรอง Java J2EE และ SOA ของ Edureka ออกแบบมาสำหรับนักเรียนและผู้เชี่ยวชาญที่ต้องการเป็น Java Developer หลักสูตรนี้ออกแบบมาเพื่อให้คุณเริ่มต้นการเขียนโปรแกรม Java และฝึกอบรมแนวคิด Java ทั้งหลักและขั้นสูงพร้อมกับเฟรมเวิร์ก Java ต่างๆเช่น Hibernate & Spring 
 มีคำถามสำหรับเรา? โปรดระบุไว้ในส่วนความคิดเห็นของบล็อก 'Java ArrayList' และเราจะติดต่อกลับโดยเร็วที่สุด