คำแนะนำเกี่ยวกับ Heaps ใน Python

บทนำ

ลองนึกภาพสนามบินที่พลุกพล่านซึ่งมีเที่ยวบินขึ้นและลงจอดทุกนาที เช่นเดียวกับที่ผู้ควบคุมการจราจรทางอากาศจัดลำดับความสำคัญของเที่ยวบินโดยอิงจากความเร่งด่วน ฮีปก็ช่วยให้เราจัดการและประมวลผลข้อมูลตามเกณฑ์เฉพาะ ทำให้มั่นใจได้ว่าชิ้นส่วนของข้อมูลที่ "ด่วน" หรือ "สำคัญ" ที่สุดจะสามารถเข้าถึงได้ที่ด้านบนเสมอ

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

ฮีปคืออะไร?

สิ่งแรกที่คุณต้องเข้าใจก่อนที่จะเจาะลึกเกี่ยวกับการใช้ฮีปคือ ฮีปคืออะไร. ฮีปมีความโดดเด่นในโลกของโครงสร้างข้อมูลในฐานะโรงไฟฟ้าที่ใช้ต้นไม้ซึ่งมีความเชี่ยวชาญเป็นพิเศษ รักษาความสงบเรียบร้อยและลำดับชั้น. แม้ว่ามันอาจจะดูคล้ายกับต้นไม้ไบนารีในสายตาที่ไม่ได้รับการฝึกฝน แต่ความแตกต่างในโครงสร้างและกฎเกณฑ์ที่ควบคุมก็ทำให้มันแตกต่างอย่างชัดเจน

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

อย่างไรก็ตาม สาระสำคัญที่แท้จริงของฮีปนั้นอยู่ที่ตัวมัน การสั่งซื้อ. ใน กองสูงสุดค่าใดๆ ของโหนดที่กำหนดจะเกินหรือเท่ากับค่าของโหนดย่อย โดยวางตำแหน่งองค์ประกอบที่ใหญ่ที่สุดไว้ที่ราก ในทางกลับกัน ก ฮีปขั้นต่ำ ทำงานบนหลักการตรงกันข้าม: ค่าของโหนดใดๆ ก็ตามจะน้อยกว่าหรือเท่ากับค่าของลูกๆ เพื่อให้แน่ใจว่าองค์ประกอบที่เล็กที่สุดอยู่ที่ราก

ในขณะที่เราดำเนินการ เราจะเจาะลึกลงไปว่าคุณสมบัติโดยธรรมชาติของฮีปเหล่านี้ช่วยให้การดำเนินงานมีประสิทธิภาพได้อย่างไร และ Python heapq โมดูลผสานรวมฮีปเข้ากับความพยายามในการเขียนโค้ดของเราได้อย่างราบรื่น

ลักษณะและคุณสมบัติของฮีป

ฮีปซึ่งมีโครงสร้างและหลักการจัดลำดับที่เป็นเอกลักษณ์ ทำให้เกิดชุดคุณลักษณะและคุณสมบัติที่แตกต่างกันออกไป ซึ่งทำให้ฮีปเหล่านี้มีคุณค่าในสถานการณ์การคำนวณต่างๆ

ก่อนอื่นกองคือ มีประสิทธิภาพโดยเนื้อแท้. โครงสร้างแบบต้นไม้ โดยเฉพาะรูปแบบไบนารีทรีที่สมบูรณ์ ช่วยให้มั่นใจได้ว่าการดำเนินการ เช่น การแทรกและการแยกองค์ประกอบลำดับความสำคัญ (สูงสุดหรือต่ำสุด) สามารถทำได้ในเวลาลอการิทึม โดยทั่วไป O (บันทึก n). ประสิทธิภาพนี้เป็นประโยชน์สำหรับอัลกอริธึมและแอปพลิเคชันที่ต้องการการเข้าถึงองค์ประกอบลำดับความสำคัญบ่อยครั้ง

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

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

นอกจากนี้ยังมีกองอีกด้วย อเนกประสงค์. แม้ว่าฮีปไบนารี่ (โดยที่ผู้ปกครองแต่ละคนมีลูกมากที่สุดสองคน) จะเป็นประเภทที่พบบ่อยที่สุด แต่ฮีปสามารถสรุปโดยทั่วไปได้ว่ามีลูกมากกว่าสองคน หรือที่เรียกว่า ฮีป d-ary. ความยืดหยุ่นนี้ช่วยให้ปรับแต่งได้อย่างละเอียดตามกรณีการใช้งานเฉพาะและข้อกำหนดด้านประสิทธิภาพ

สุดท้ายก็มีกองอยู่ ปรับตัวเอง. เมื่อใดก็ตามที่มีการเพิ่มหรือลบองค์ประกอบ โครงสร้างจะจัดเรียงตัวเองใหม่เพื่อรักษาคุณสมบัติไว้ การปรับสมดุลแบบไดนามิกนี้ช่วยให้แน่ใจว่าฮีปยังคงได้รับการปรับให้เหมาะสมสำหรับการดำเนินการหลักตลอดเวลา

เมื่อเราเจาะลึกลงไปถึงการใช้งาน Python และการใช้งานจริง ศักยภาพที่แท้จริงของฮีปก็จะปรากฏต่อหน้าเรา

ประเภทของฮีป

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

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

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

นอกเหนือจากหมวดหมู่หลักเหล่านี้แล้ว ฮีปยังสามารถแยกแยะได้ตามปัจจัยการแตกแขนง:

แม้ว่าฮีปไบนารีจะพบได้บ่อยที่สุด โดยผู้ปกครองแต่ละคนจะมีลูกไม่เกินสองคน แนวคิดของฮีปสามารถขยายไปยังโหนดที่มีลูกมากกว่าสองคนได้ ใน ฮีป d-aryแต่ละโหนดมีมากที่สุด d เด็ก. การเปลี่ยนแปลงนี้สามารถปรับให้เหมาะสมสำหรับสถานการณ์เฉพาะ เช่น ลดความสูงของต้นไม้เพื่อเร่งการดำเนินการบางอย่าง

ฮีปทวินาม คือชุดของต้นไม้ทวินามที่ถูกกำหนดแบบวนซ้ำ ฮีปทวินามถูกใช้ในการใช้งานคิวลำดับความสำคัญและให้การดำเนินการผสานที่มีประสิทธิภาพ

ตั้งชื่อตามลำดับฟีโบนัชชีอันโด่งดัง กองฟีโบนัชชี นำเสนอเวลาการทำงานที่ตัดจำหน่ายได้ดีกว่าสำหรับการดำเนินการหลายอย่าง เมื่อเปรียบเทียบกับฮีปไบนารีหรือทวินาม มีประโยชน์อย่างยิ่งในอัลกอริธึมการเพิ่มประสิทธิภาพเครือข่าย

การใช้งานฮีปของ Python - The ฮีปคิว โมดูล

Python นำเสนอโมดูลในตัวสำหรับการดำเนินการฮีป - heapq โมดูล. โมดูลนี้มีคอลเลกชันของฟังก์ชันที่เกี่ยวข้องกับฮีป ซึ่งช่วยให้นักพัฒนาสามารถแปลงรายการเป็นฮีปและดำเนินการฮีปต่างๆ ได้โดยไม่จำเป็นต้องใช้งานแบบกำหนดเอง เรามาเจาะลึกถึงความแตกต่างของโมดูลนี้ และวิธีที่โมดูลนี้มอบพลังแห่งฮีปให้กับคุณ

พื้นที่ heapq โมดูลไม่ได้ระบุประเภทข้อมูลฮีปที่แตกต่างกัน แต่กลับนำเสนอฟังก์ชันที่ทำงานบนรายการ Python ทั่วไป โดยเปลี่ยนและถือว่ารายการเหล่านั้นเป็น ฮีปไบนารี.

วิธีการนี้มีทั้งประสิทธิภาพของหน่วยความจำและผสานรวมเข้ากับโครงสร้างข้อมูลที่มีอยู่ของ Python ได้อย่างราบรื่น

นั่นหมายความว่า ฮีปจะแสดงเป็นรายการ in heapq. ความงดงามของการเป็นตัวแทนนี้คือความเรียบง่าย - ระบบดัชนีรายการแบบศูนย์ทำหน้าที่เป็นแผนผังไบนารีโดยนัย สำหรับองค์ประกอบใดๆ ที่ตำแหน่งที่กำหนด i, ของมัน:

• ลูกซ้ายอยู่ในตำแหน่ง 2*i + 1
• ลูกขวาอยู่ในตำแหน่ง 2*i + 2
• โหนดหลักอยู่ที่ตำแหน่ง (i-1)//2

โครงสร้างโดยนัยนี้ช่วยให้มั่นใจได้ว่าไม่จำเป็นต้องมีการแสดงไบนารีทรีแบบอิงโหนดแยกต่างหาก ทำให้การดำเนินการตรงไปตรงมาและใช้หน่วยความจำน้อยที่สุด

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

Python ของ heapq โมดูลมีชุดฟังก์ชันที่ช่วยให้นักพัฒนาสามารถดำเนินการฮีปต่างๆ ในรายการได้

ในส่วนต่อไปนี้ เราจะเจาะลึกการดำเนินการพื้นฐานแต่ละอย่างอย่างละเอียด โดยสำรวจกลไกและกรณีการใช้งาน

วิธีแปลงรายการให้เป็นฮีป

พื้นที่ heapify() function เป็นจุดเริ่มต้นสำหรับงานที่เกี่ยวข้องกับฮีปมากมาย ใช้เวลาทำซ้ำได้ (โดยทั่วไปคือรายการ) และจัดเรียงองค์ประกอบใหม่เพื่อให้ตรงตามคุณสมบัติของฮีปขั้นต่ำ:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

สิ่งนี้จะส่งออกรายการที่เรียงลำดับใหม่ซึ่งแสดงถึงฮีปขั้นต่ำที่ถูกต้อง:

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

วิธีเพิ่มองค์ประกอบให้กับฮีป

พื้นที่ heappush() ฟังก์ชันช่วยให้คุณสามารถแทรกองค์ประกอบใหม่ลงในฮีปในขณะที่ยังคงคุณสมบัติของฮีปไว้:

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

การรันโค้ดจะทำให้คุณมีรายการองค์ประกอบที่รักษาคุณสมบัติ min heap:

[3, 5, 7]

วิธีการลบและส่งคืนองค์ประกอบที่เล็กที่สุดออกจากฮีป

พื้นที่ heappop() ฟังก์ชั่นแยกและส่งกลับองค์ประกอบที่เล็กที่สุดจากฮีป (รูทในฮีปขั้นต่ำ) หลังจากลบออกแล้ว จะช่วยให้แน่ใจว่ารายการยังคงเป็นฮีปที่ถูกต้อง:

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

สิ่งนี้จะแสดงองค์ประกอบที่เล็กที่สุดและรายการที่เหลือ:

1
[3, 7, 5, 9]

ที่นี่ 1 เป็นองค์ประกอบที่เล็กที่สุดจาก heapและรายการที่เหลือยังคงรักษาคุณสมบัติฮีปไว้ แม้ว่าเราจะลบออกแล้วก็ตาม 1.

วิธีดันไอเท็มใหม่และป๊อปไอเท็มที่เล็กที่สุด

พื้นที่ heappushpop() function คือการดำเนินการแบบรวมที่จะผลักรายการใหม่ไปยังฮีป จากนั้นป๊อปอัปและส่งคืนรายการที่เล็กที่สุดจากฮีป:

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

สิ่งนี้จะออก 3องค์ประกอบที่เล็กที่สุดแล้วพิมพ์ออกมาใหม่ heap รายการที่ตอนนี้รวมอยู่ด้วย 4 ในขณะที่ยังคงรักษาคุณสมบัติฮีปไว้:

3
[4, 5, 7, 9]

วิธีเปลี่ยนสิ่งของที่เล็กที่สุดและดันสิ่งของใหม่

พื้นที่ heapreplace() ฟังก์ชันป๊อปอัปองค์ประกอบที่เล็กที่สุดและพุชองค์ประกอบใหม่ลงบนฮีป ทั้งหมดในการดำเนินการที่มีประสิทธิภาพเพียงครั้งเดียว:

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

พิมพ์นี้ 1องค์ประกอบที่เล็กที่สุด และตอนนี้รายการรวม 4 และรักษาคุณสมบัติฮีป:

1
[4, 5, 7, 9]

ค้นหาความสุดขั้วหลายประการในฮีปของ Python

nlargest(n, iterable[, key]) และ nsmallest(n, iterable[, key]) ฟังก์ชั่นได้รับการออกแบบเพื่อดึงองค์ประกอบที่ใหญ่ที่สุดหรือเล็กที่สุดหลายรายการจากการทำซ้ำได้ สิ่งเหล่านี้มีประสิทธิภาพมากกว่าการเรียงลำดับการทำซ้ำทั้งหมดได้ เมื่อคุณต้องการค่าที่มากเกินไปเพียงไม่กี่ค่าเท่านั้น ตัวอย่างเช่น สมมติว่าคุณมีรายการต่อไปนี้ และคุณต้องการค้นหาค่าที่เล็กที่สุดและใหญ่ที่สุดสามค่าในรายการ:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

ที่นี่ nlargest() และ nsmallest() ฟังก์ชั่นต่างๆ มีประโยชน์:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

ซึ่งจะให้คุณสองรายการ - รายการหนึ่งมีค่ามากที่สุดสามค่า และอีกรายการหนึ่งมีค่าน้อยที่สุดสามค่าจาก data รายการ:

[9, 6, 5]
[1, 1, 2]

วิธีสร้างฮีปที่คุณกำหนดเอง

ในขณะที่ Python heapq โมดูลมีชุดเครื่องมือที่มีประสิทธิภาพสำหรับการทำงานกับฮีป มีสถานการณ์ที่พฤติกรรมฮีปขั้นต่ำเริ่มต้นอาจไม่เพียงพอ ไม่ว่าคุณกำลังมองหาการใช้ฮีปสูงสุดหรือต้องการฮีปที่ทำงานตามฟังก์ชันการเปรียบเทียบที่กำหนดเอง การสร้างฮีปที่กำหนดเองอาจเป็นคำตอบได้ มาดูวิธีปรับแต่งฮีปให้ตรงกับความต้องการเฉพาะกัน

การใช้ Max Heap โดยใช้ heapq

โดยค่าเริ่มต้น heapq สร้าง ฮีปขั้นต่ำ. อย่างไรก็ตาม ด้วยเคล็ดลับง่ายๆ คุณสามารถใช้มันเพื่อใช้งานฮีปสูงสุดได้ แนวคิดคือการกลับลำดับขององค์ประกอบโดยการคูณพวกมันด้วย -1 ก่อนที่จะเพิ่มลงในฮีป:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

ด้วยวิธีนี้ จำนวนที่มากที่สุด (ในแง่ของมูลค่าสัมบูรณ์) จะกลายเป็นค่าที่น้อยที่สุด ทำให้สามารถ heapq ฟังก์ชั่นเพื่อรักษาโครงสร้างฮีปสูงสุด

ฮีปพร้อมฟังก์ชันการเปรียบเทียบแบบกำหนดเอง

บางครั้งคุณอาจต้องการฮีปที่ไม่เพียงแต่เปรียบเทียบตามลำดับองค์ประกอบตามธรรมชาติเท่านั้น ตัวอย่างเช่น หากคุณกำลังทำงานกับออบเจ็กต์ที่ซับซ้อนหรือมีเกณฑ์การเรียงลำดับที่เฉพาะเจาะจง ฟังก์ชันการเปรียบเทียบแบบกำหนดเองจะมีความสำคัญ

เพื่อให้บรรลุเป้าหมายนี้ คุณสามารถรวมองค์ประกอบในคลาสตัวช่วยที่แทนที่ตัวดำเนินการเปรียบเทียบ:

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

ด้วยการตั้งค่านี้ คุณสามารถกำหนดฟังก์ชันตัวเปรียบเทียบที่กำหนดเองและใช้กับฮีปได้

สรุป

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

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

• เนื้อหาที่ขับเคลื่อนด้วย SEO และการเผยแพร่ประชาสัมพันธ์ รับการขยายวันนี้
• PlatoData.Network Vertical Generative Ai เพิ่มพลังให้กับตัวเอง เข้าถึงได้ที่นี่.
• เพลโตไอสตรีม. Web3 อัจฉริยะ ขยายความรู้ เข้าถึงได้ที่นี่.
• เพลโตESG. คาร์บอน, คลีนเทค, พลังงาน, สิ่งแวดล้อม แสงอาทิตย์, การจัดการของเสีย. เข้าถึงได้ที่นี่.
• เพลโตสุขภาพ เทคโนโลยีชีวภาพและข่าวกรองการทดลองทางคลินิก เข้าถึงได้ที่นี่.
• ที่มา: https://stackabuse.com/guide-to-heaps-in-python/