คิวฮีปเป็นโครงสร้างทรีพิเศษซึ่งแต่ละโหนดหลักมีค่าน้อยกว่าหรือเท่ากับโหนดย่อย ใน python จะถูกใช้งานโดยใช้โมดูล heapq มีประโยชน์มากคือการนำคิวที่มีลำดับความสำคัญไปใช้โดยที่รายการคิวที่มีน้ำหนักสูงกว่าจะได้รับการจัดลำดับความสำคัญในการประมวลผลมากกว่า
สร้างฮีป
คิวฮีปถูกสร้างขึ้นโดยใช้ไลบรารี inbuilt ของ python ชื่อ heapq ไลบรารีนี้มีฟังก์ชันที่เกี่ยวข้องเพื่อดำเนินการต่างๆ บนโครงสร้างข้อมูลแบบฮีป ด้านล่างนี้คือรายการฟังก์ชันเหล่านี้
- ทำให้เป็นก้อน – ฟังก์ชันนี้แปลงรายการปกติเป็นฮีป ในฮีปที่เป็นผลลัพธ์ องค์ประกอบที่เล็กที่สุดจะถูกผลักไปที่ตำแหน่งดัชนี 0 แต่องค์ประกอบข้อมูลที่เหลือไม่จำเป็นต้องถูกจัดเรียง
- ฮีปพุช – ฟังก์ชันนี้เพิ่มองค์ประกอบให้กับฮีปโดยไม่เปลี่ยนแปลงฮีปปัจจุบัน
- ฮีปป็อป – ฟังก์ชันนี้จะคืนค่าองค์ประกอบข้อมูลที่เล็กที่สุดจากฮีป
- ฮีปเพลส – ฟังก์ชันนี้จะแทนที่องค์ประกอบข้อมูลที่เล็กที่สุดด้วยค่าใหม่ที่ให้มาในฟังก์ชัน
สร้างกอง
ฮีปถูกสร้างขึ้นโดยเพียงแค่ใช้รายการองค์ประกอบที่มีฟังก์ชัน heapify ในตัวอย่างด้านล่าง เราจัดเตรียมรายการองค์ประกอบและฟังก์ชัน heapify จะจัดเรียงองค์ประกอบใหม่โดยนำองค์ประกอบที่เล็กที่สุดไปยังตำแหน่งแรก
ตัวอย่าง
import heapq H = [21,1,45,78,3,5] # Use heapify to rearrange the elements heapq.heapify(H) print(H)
ผลลัพธ์
เมื่อโค้ดด้านบนถูกรัน มันจะให้ผลลัพธ์ดังต่อไปนี้ −
[1, 3, 5, 78, 21, 45]
การแทรกลงในฮีป
การแทรกองค์ประกอบข้อมูลลงในฮีปจะเพิ่มองค์ประกอบที่ดัชนีสุดท้ายเสมอ แต่คุณสามารถใช้ฟังก์ชัน heapify อีกครั้งเพื่อนำองค์ประกอบที่เพิ่มใหม่ไปยังดัชนีแรกได้ก็ต่อเมื่อมีค่าน้อยที่สุด ในตัวอย่างด้านล่าง เราใส่ตัวเลข 8
ตัวอย่าง
import heapq H = [21,1,45,78,3,5] # Covert to a heap heapq.heapify(H) print(H) # Add element heapq.heappush(H,8) print(H)
ผลลัพธ์
เมื่อโค้ดด้านบนถูกรัน มันจะให้ผลลัพธ์ดังต่อไปนี้ −
[1, 3, 5, 78, 21, 45] [1, 3, 5, 78, 21, 45, 8]
การนำออกจากฮีป
คุณสามารถลบองค์ประกอบที่ดัชนีแรกได้โดยใช้ฟังก์ชันนี้ ในตัวอย่างด้านล่าง ฟังก์ชันจะลบองค์ประกอบที่ตำแหน่งดัชนี 1 เสมอ
ตัวอย่าง
import heapq H = [21,1,45,78,3,5] # Create the heap heapq.heapify(H) print(H) # Remove element from the heap heapq.heappop(H) print(H)
ผลลัพธ์
เมื่อโค้ดด้านบนถูกรัน มันจะให้ผลลัพธ์ดังต่อไปนี้ −
[1, 3, 5, 78, 21, 45] [3, 21, 5, 78, 45]
การแทนที่ในกอง
ฟังก์ชัน heapreplace จะลบองค์ประกอบที่เล็กที่สุดของฮีปเสมอ และแทรกองค์ประกอบที่เข้ามาใหม่ในตำแหน่งใดตำแหน่งหนึ่งที่ไม่ได้รับการแก้ไขโดยลำดับใดๆ
ตัวอย่าง
import heapq H = [21,1,45,78,3,5] # Create the heap heapq.heapify(H) print(H) # Replace an element heapq.heapreplace(H,6) print(H)
ผลลัพธ์
เมื่อโค้ดด้านบนถูกรัน มันจะให้ผลลัพธ์ดังต่อไปนี้ −
[1, 3, 5, 78, 21, 45] [3, 6, 5, 78, 21, 45]
