หมายเหตุ: นี่เป็นสำหรับผู้ที่ทราบวิธีการใช้โครงสร้างข้อมูลฮีปโดยไม่ต้องใช้ไลบรารีใด ๆ ถ้าไม่เช่นนั้น ฉันแนะนำให้เรียนรู้และทำความเข้าใจการทำงานภายในของฮีป

ฮีปคือโครงสร้างข้อมูลแบบทรีซึ่งโหนดทั้งหมดของทรีอยู่ในลำดับเฉพาะ โดยพื้นฐานแล้วมันเป็นไบนารีทรีที่สมบูรณ์ซึ่งตอบสนองคุณสมบัติของฮีป เช่น min-heap และ max-heap

ฮีปถูกใช้ในอัลกอริธึมที่มีชื่อเสียงมากมาย เช่น อัลกอริทึมของ Dijkstra สำหรับการค้นหาเส้นทางที่สั้นที่สุด อัลกอริธึมการเรียงลำดับฮีป การใช้ คิวลำดับความสำคัญ และอื่นๆ โดยพื้นฐานแล้ว ฮีปคือโครงสร้างข้อมูลที่คุณจะใช้ เมื่อคุณต้องการเข้าถึงองค์ประกอบขั้นต่ำหรือสูงสุดอย่างรวดเร็ว

  1. Min-heap: เป็นคุณสมบัติฮีปที่องค์ประกอบหลักมีขนาดเล็กที่สุดในบรรดาลูกด้านซ้ายและขวา และองค์ประกอบรากมีขนาดเล็กที่สุดในบรรดาองค์ประกอบทั้งหมด องค์ประกอบ
  2. Max-heap: ในคุณสมบัตินี้ องค์ประกอบหลัก ใหญ่ที่สุดในบรรดาลูกด้านซ้ายและขวา และองค์ประกอบรูทนั้นใหญ่ที่สุดในบรรดาองค์ประกอบทั้งหมด

ไลบรารีสำหรับใช้งาน min-heap และ max-heap:

“heapq”การใช้ไลบรารีนี้ทำให้เราสามารถจัดการกับการดำเนินการที่ดำเนินการบนฮีปได้

heapq.heapify(listForTree)ใช้สำหรับการสร้าง min-heap โดยจะใช้รายการเป็นพารามิเตอร์

heapq._heapify_max(listForTree) ใช้สำหรับการสร้างฮีปสูงสุด โดยจะใช้รายการเป็นพารามิเตอร์

heapq.heappop(minheap) ใช้เพื่อแสดงองค์ประกอบจาก min-heap ความแตกต่างระหว่างปกติ pop() และ heappop()คือหลังจากฟังก์ชัน heappopคุณสมบัติฮีปของรายการที่กำหนดจะยังคงอยู่ มันจะส่งคืนองค์ประกอบรากที่เล็กที่สุดของต้นไม้

heapq._heappop_max(maxheap) ฟังก์ชันป๊อปนี้จะแสดงองค์ประกอบรูท เช่น องค์ประกอบที่ใหญ่ที่สุดในแผนผัง และหลังจากฟังก์ชันป๊อป คุณสมบัติฮีปจะถูกคงไว้

หากต้องการดูวิธีการทั้งหมดที่คุณสามารถใช้ได้กับ heapq โปรดดูที่ เอกสาร Python เกี่ยวกับ heapq

ขอบคุณที่อ่าน!