ฮีป (โครงสร้างข้อมูล)

Q: การใช้งานโดยใช้อาร์เรย์

โดยทั่วไปแล้ว ฮีปจะถูกสร้างโดยใช้ อาร์เรย์ ดังนี้:

Q: ตัวแปร

กอง 2–3 กอง กองบี บี๊บ ฮีปไบนารี กองทวินาม คิวบรอดัล กอง d -ary กองฟิโบนาชี่ คีดี ฮีป กองใบไม้ กองของฝ่ายซ้าย กองทวินามแบบเบี่ยงเบน กองฟิโบนาชี่ที่เข้มงวด ฮีปแบบมิน-แม็กซ์ ฮีปจับคู่ ฮีปเรดิกซ์ กองหลอมรวมแบบสุ่ม กองเอียง กองอ่อน กองสามชั้น ทรีป กองที่อ่อนแอ

ตัวอย่างของ max-heap แบบไบนารีโดยที่คีย์ของโหนดเป็นจำนวนเต็มระหว่าง 1 ถึง 100

ในวิทยาการคอมพิวเตอร์ฮีปเป็นโครงสร้างข้อมูลแบบต้นไม้ที่ตรงตามคุณสมบัติของฮีป : ในแม็กซ์ฮีปสำหรับโหนด C ใดๆ หาก P เป็นโหนดแม่ของ C แล้วคีย์ ( ค่า ) ของ P จะมากกว่าหรือเท่ากับคีย์ของ C ในมินฮีปคีย์ของ P จะน้อยกว่าหรือเท่ากับคีย์ของ C ^[¹^]โหนดที่ "ด้านบน" ของฮีป (ที่ไม่มีโหนดแม่) เรียกว่าโหนดราก

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

การใช้งานฮีปที่พบได้ทั่วไปคือฮีปไบนารีซึ่งต้นไม้เป็น ต้นไม้ไบนารี ที่สมบูรณ์^{[ 2 ]} (ดูรูป) โครงสร้างข้อมูลฮีป โดยเฉพาะฮีปไบนารี ได้รับการแนะนำโดยJWJ Williamsในปี 1964 ในฐานะโครงสร้างข้อมูลสำหรับอัลกอริทึมการเรียงลำดับฮีป ซอร์ต ^{[ 3 ]}ฮีปยังมีความสำคัญอย่างยิ่งในอัลกอริทึมกราฟ ที่มีประสิทธิภาพหลายอย่าง เช่นอัลกอริทึมของ Dijkstraเมื่อฮีปเป็นต้นไม้ไบนารีที่สมบูรณ์ ฮีปจะมีระดับความสูงที่น้อยที่สุดที่เป็นไปได้ ฮีปที่มี โหนด Nและกิ่ง สำหรับแต่ละโหนดจะมี ระดับความสูงlog N เสมอ

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

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

การดำเนินงาน

การดำเนินการทั่วไปที่เกี่ยวข้องกับฮีป ได้แก่:

พื้นฐาน

find-max (หรือfind-min ): ค้นหาค่าสูงสุดของ max-heap หรือค่าต่ำสุดของ min-heap ตามลำดับ (หรือเรียกอีกอย่างว่าpeek )
แทรก : เพิ่มคีย์ใหม่ลงในฮีป (หรือ เรียกอีกอย่างว่า พุช^{[ 4 ]} )
extract-max (หรือextract-min ): ส่งคืนโหนดที่มีค่าสูงสุดจากฮีปสูงสุด [หรือค่าต่ำสุดจากฮีปต่ำสุด] หลังจากลบออกจากฮีป (หรือpop ^{[ 5 ]} )
delete-max (หรือdelete-min ): คำสั่งที่ใช้ลบโหนดรากของ max heap (หรือ min heap) ตามลำดับ
แทนที่ : ดึงรูทออกและผลักคีย์ใหม่เข้าไป วิธีนี้มีประสิทธิภาพมากกว่าการดึงออกแล้วตามด้วยการเพิ่มเข้าไป เนื่องจากต้องปรับสมดุลเพียงครั้งเดียว ไม่ใช่สองครั้ง และเหมาะสมสำหรับฮีปที่มีขนาดคงที่^{[ 6 ]}

การสร้างสรรค์

create-heap : สร้างฮีปว่างเปล่า
heapify : สร้างฮีปจากอาร์เรย์ขององค์ประกอบที่กำหนด
ผสาน ( รวม ): การรวมฮีปสองฮีปเข้าด้วยกันเพื่อสร้างฮีปใหม่ที่ถูกต้อง ซึ่งประกอบด้วยองค์ประกอบทั้งหมดของทั้งสองฮีป โดยคงฮีปเดิมไว้
ผสาน (meld) : การรวมฮีปสองฮีปเข้าด้วยกันเพื่อสร้างฮีปใหม่ที่ถูกต้อง ซึ่งประกอบด้วยองค์ประกอบทั้งหมดของทั้งสองฮีป และทำลายฮีปเดิม

การตรวจสอบ

ขนาด : ส่งคืนจำนวนรายการในฮีป
is-empty : ส่งคืนค่า true ถ้าฮีปว่างเปล่า และ false ถ้าไม่ใช่

ภายใน

increase-keyหรือdecrease-key : การอัปเดตค่าคีย์ภายใน max-heap หรือ min-heap ตามลำดับ
ลบ : ลบโหนดใดๆ (จากนั้นย้ายโหนดสุดท้ายและคัดกรองเพื่อรักษาสภาพของฮีป)
sift-up : ย้ายโหนดขึ้นไปในโครงสร้างต้นไม้ ตราบเท่าที่จำเป็น ใช้เพื่อคืนค่าสภาพของฮีปหลังจากแทรกโหนด เรียกว่า "sift" เพราะโหนดจะเคลื่อนขึ้นไปในโครงสร้างต้นไม้จนกว่าจะถึงระดับที่ถูกต้อง เหมือนกับการร่อนตะแกรง
sift-down : ย้ายโหนดลงในโครงสร้างต้นไม้ คล้ายกับ sift-up ใช้เพื่อคืนค่าสภาพของฮีปหลังจากลบหรือแทนที่โหนด

การใช้งานโดยใช้อาร์เรย์

โดยทั่วไปแล้ว ฮีปจะถูกสร้างโดยใช้อาร์เรย์ดังนี้:

แต่ละองค์ประกอบในอาร์เรย์แสดงถึงโหนดของฮีป และ
ความสัมพันธ์ระหว่างพ่อ/ลูกถูกกำหนดโดยปริยายจากดัชนีขององค์ประกอบในอาร์เรย์

ตัวอย่างของ max-heap แบบไบนารีที่สมบูรณ์ โดยมีคีย์ของโหนดเป็นจำนวนเต็มตั้งแต่ 1 ถึง 100 และวิธีการจัดเก็บในอาร์เรย์

สำหรับฮีปแบบไบนารีในอาร์เรย์ ดัชนีแรกจะประกอบด้วยองค์ประกอบราก ดัชนีสองตัวถัดไปจะประกอบด้วยลูกของราก ดัชนีสี่ตัวถัดไปจะประกอบด้วยลูกสี่ตัวของโหนดลูกสองตัวของราก และเป็นเช่นนี้เรื่อยไป ดังนั้น เมื่อกำหนดโหนดที่ดัชนี $i$ ลูกของมันจะอยู่ที่ดัชนี⁠ $2i+1$ และ $2i+2$ และองค์ประกอบแม่ของมันอยู่ที่ดัชนี ⌊ $(i -1)/2⌋$ ในอาร์เรย์ที่เริ่มต้นจากดัชนี ⁠ $0$ หรือที่ $2i$ , ⁠ $2i+1$ และ ⌊ $i / 2⌋$ ตามลำดับ ในอาร์เรย์ที่เริ่มต้นจาก $1$ ระบบการจัดทำดัชนีแบบง่ายนี้ทำให้การเดิน "ขึ้น" หรือ "ลง" ในโครงสร้างต้นไม้มีประสิทธิภาพมากขึ้น

การปรับสมดุลฮีปทำได้โดยการดำเนินการ sift-up หรือ sift-down (การสลับองค์ประกอบที่ไม่อยู่ในลำดับที่ถูกต้อง) เนื่องจากเราสามารถสร้างฮีปจากอาร์เรย์ได้โดยไม่ต้องใช้หน่วยความจำเพิ่มเติม (เช่น สำหรับโหนด) ดังนั้นheapsortจึงสามารถใช้ในการเรียงลำดับอาร์เรย์ในตำแหน่งเดิมได้

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

แม้ว่าฮีปประเภทต่างๆ จะดำเนินการแตกต่างกัน แต่โดยทั่วไปแล้ววิธีการที่ใช้กันมากที่สุดมีดังนี้:

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

การสร้างฮีปไบนารี (หรือd -ary) จากอาร์เรย์ขององค์ประกอบที่กำหนดอาจดำเนินการได้ในเวลาเชิงเส้นโดยใช้อัลกอริทึม Floyd แบบคลาสสิก โดยจำนวนการเปรียบเทียบในกรณีที่เลวร้ายที่สุดเท่ากับ 2 N − 2 s ( N ) − e ( N ) (สำหรับฮีปไบนารี) โดยที่s ( N ) คือผลรวมของตัวเลขทั้งหมดของการแสดงไบนารีของNและe ( N ) คือเลขชี้กำลังของ 2 ในการแยกตัวประกอบเฉพาะของN [ ⁷^{] ซึ่งเร็วกว่าลำดับของการแทรกต่อเนื่องลงในฮี}^ปที่ว่างเปล่าในตอนแรก ซึ่งเป็นแบบลอการิทึมเชิงเส้น^{[ a ]}

การเปรียบเทียบขอบเขตทางทฤษฎีสำหรับตัวแปรต่างๆ

ต่อไปนี้เป็นความซับซ้อนของเวลา^{[ 8 ]}ของโครงสร้างข้อมูลฮีปต่างๆ ตัวย่อam.บ่งชี้ว่าความซับซ้อนที่กำหนดนั้นเป็นค่าเฉลี่ย มิฉะนั้นจะเป็นความซับซ้อนในกรณีที่เลวร้ายที่สุด สำหรับความหมายของ " O ( f )" และ " Θ ( f )" โปรดดูสัญกรณ์ Big Oชื่อของการดำเนินการนั้นถือว่าใช้ฮีปสูงสุด

การดำเนินการ	หาค่าสูงสุด	ลบสูงสุด	เพิ่มคีย์	แทรก	หลอมรวม	กองรวม^[ข]
ไบนารี^{[ 8 ]}	Θ (1)	Θ (log n )	Θ (log n )	Θ (log n )	Θ ( n )	Θ ( n )
เบี่ยงเบน^{[ 9 ]}	Θ (1)	O (log n ) am.	O (log n ) am.	O (log n ) am.	O (log n ) am.	Θ ( n ) am.
ฝ่ายซ้าย^{[ 10 ]}	Θ (1)	Θ (log n )	Θ (log n )	Θ (log n )	Θ (log n )	Θ ( n )
ทวินาม^{[ 8 ]}^{[ 12 ]}	Θ (1)	Θ (log n )	Θ (log n )	Θ (1) am.	Θ (log n ) ^[^c^]	Θ ( n )
ทวินามแบบเบี่ยงเบน^{[ 13 ]}	Θ (1)	Θ (log n )	Θ (log n )	Θ (1)	Θ (log n ) ^[^c^]	Θ ( n )
กอง 2–3 กอง^{[ 15 ]}	Θ (1)	O (log n ) am.	Θ (1)	Θ (1) am.	O (log n ) ^[^c^]	Θ ( n )
ความเบี่ยงเบนจากล่างขึ้นบน^{[ 9 ]}	Θ (1)	O (log n ) am.	O (log n ) am.	Θ (1) am.	Θ (1) am.	Θ ( n ) am.
การจับคู่^{[ 16 ]}	Θ (1)	O (log n ) am.	o (log n ) am. ^[^d^]	Θ (1)	Θ (1)	Θ ( n )
การจับคู่ลำดับ^{[ 19 ]}	Θ (1)	O (log n ) am.	Θ (1) am.	Θ (1)	Θ (1)	Θ ( n )
ฟิโบนาชชี^{[ 8 ]}^{[ 20 ]}	Θ (1)	O (log n ) am.	Θ (1) am.	Θ (1)	Θ (1)	Θ ( n )
ฟิโบนาชชีที่เข้มงวด^{[ 21 ]}^{[ e ]}	Θ (1)	Θ (log n )	Θ (1)	Θ (1)	Θ (1)	Θ ( n )
บรอดัล^{[ 22 ]}^{[ e ]}	Θ (1)	Θ (log n )	Θ (1)	Θ (1)	Θ (1)	Θ ( n ) ^{[ 23 ]}

↑การแทรกแต่ละครั้งใช้เวลา O(log( k )) ในขนาดฮีปที่มีอยู่ ดังนั้น $\sum _{k=1}^{n}O(\log k)$ . เนื่องจาก $\log n/2=(\log n)-1$ โดยที่ค่าคงที่ (ครึ่งหนึ่ง) ของการแทรกเหล่านี้จะอยู่ภายในค่าคงที่จากค่าสูงสุด ดังนั้นในเชิงอนุกรมวิธานเราสามารถสมมติได้ว่า $k=n$ อย่างเป็นทางการแล้ว เวลาคือ $nO(\log n)-O(n)=O(n\log n)$ สิ่งนี้สามารถเห็นได้ชัดเจนจากค่าประมาณของสเตอร์ลิง เช่น กัน
↑การสร้างฮีป (make-heap)คือการดำเนินการสร้างฮีปจากลำดับของ องค์ประกอบที่ไม่เรียงลำดับจำนวน nรายการ สามารถทำได้ใน เวลา Θ ( n ) เมื่อใดก็ตามที่ meldทำงานใน เวลา O (log n ) (โดยที่ความซับซ้อนทั้งสองสามารถเฉลี่ยได้)^[⁹^]^[¹⁰^]อัลกอริทึมอื่นบรรลุ Θ ( n ) สำหรับฮีปไบนารี^[¹¹^]
1 2 3สำหรับ ฮีป แบบถาวร (ที่ไม่รองรับการเพิ่มคีย์ ) การแปลงทั่วไปจะลดต้นทุนของการรวมให้เท่ากับต้นทุนของการแทรกในขณะที่ต้นทุนใหม่ของการลบสูงสุดคือผลรวมของต้นทุนเดิมของการลบสูงสุดและการรวม^{[ 14 ]}ในที่นี้ จะทำให้การรวมทำงานใน เวลา Θ (1) (เฉลี่ย หากต้นทุนของการแทรกคือ) ในขณะที่การลบสูงสุดยังคงทำงานใน O (log n ) เมื่อนำไปใช้กับฮีปแบบไบโนเมียลแบบเฉียง จะได้คิว Brodal-Okasaki ซึ่งเป็นฮีปแบบถาวรที่มีความซับซ้อนในกรณีที่เลวร้ายที่สุดที่เหมาะสมที่สุด^[¹³^]
↑ขอบล่างของ $\Omega (\log \log n),$ ^{[ 17 ]}ขอบเขตบนของ $O(2^{2{\sqrt {\log \log n}}}).$ ^{[ 18 ]}
1 2คิว Brodal และฮีป Fibonacci แบบเข้มงวดบรรลุความซับซ้อนในกรณีที่เลวร้ายที่สุดที่เหมาะสมที่สุดสำหรับฮีป โดยโครงสร้างเหล่านี้ได้รับการอธิบายครั้งแรกว่าเป็นโครงสร้างข้อมูลเชิงคำสั่ง คิว Brodal-Okasaki เป็น โครงสร้างข้อมูล ถาวรที่บรรลุความเหมาะสมที่สุดเช่นเดียวกัน ยกเว้นว่าไม่รองรับการเพิ่มคีย์

แอปพลิเคชัน

โครงสร้างข้อมูลแบบฮีปมีแอปพลิเคชันมากมาย

ฮีปซอร์ต (Heapsort) : หนึ่งในวิธีการเรียงลำดับที่ดีที่สุด เนื่องจากเป็นการประมวลผลแบบ in-place และไม่มีสถานการณ์เลวร้ายที่สุดแบบกำลังสอง
อัลกอริทึมการเลือก : ฮีปช่วยให้เข้าถึงองค์ประกอบขั้นต่ำหรือสูงสุดได้ในเวลาคงที่ และการเลือกอื่นๆ (เช่น ค่ามัธยฐานหรือองค์ประกอบที่ k) สามารถทำได้ในเวลาต่ำกว่าเชิงเส้นบนข้อมูลที่อยู่ในฮีป^{[ 24 ]}
อัลกอริทึมกราฟ : การใช้ฮีปเป็นโครงสร้างข้อมูลภายในสำหรับการสำรวจ จะช่วยลดเวลาในการทำงานลงในระดับพหุนาม ตัวอย่างของปัญหาดังกล่าว ได้แก่อัลกอริทึมต้นไม้แผ่ขยายขั้นต่ำของ Primและอัลกอริทึมเส้นทางที่สั้นที่สุดของ Dijkstra
คิวลำดับความสำคัญ : คิวลำดับความสำคัญเป็นแนวคิดเชิงนามธรรมเช่นเดียวกับ "รายการ" หรือ "แผนที่" เช่นเดียวกับที่รายการสามารถนำไปใช้ได้ด้วยรายการเชื่อมโยงหรืออาร์เรย์ คิวลำดับความสำคัญก็สามารถนำไปใช้ได้ด้วยฮีปหรือวิธีการอื่นๆ อีกมากมาย
การรวมแบบ K-way : โครงสร้างข้อมูลแบบฮีปมีประโยชน์ในการรวมสตรีมข้อมูลขาเข้าที่เรียงลำดับแล้วหลายๆ สตรีมเข้าด้วยกันเป็นสตรีมข้อมูลขาออกที่เรียงลำดับแล้วเพียงสตรีมเดียว ตัวอย่างของความจำเป็นในการรวม ได้แก่ การเรียงลำดับภายนอกและผลลัพธ์แบบสตรีมมิ่งจากข้อมูลแบบกระจาย เช่น ต้นไม้รวมที่มีโครงสร้างแบบล็อก ลูปภายในจะดึงค่าต่ำสุดขององค์ประกอบ แทนที่ด้วยองค์ประกอบถัดไปสำหรับสตรีมข้อมูลขาเข้าที่สอดคล้องกัน จากนั้นจึงดำเนินการกรองลงในฮีป (หรืออาจใช้ฟังก์ชัน replace ก็ได้) (การใช้ฟังก์ชัน extract-max และ insert ของคิวลำดับความสำคัญนั้นมีประสิทธิภาพน้อยกว่ามาก)

การนำภาษาโปรแกรมไปใช้

ไลบรารีมาตรฐาน ของC++มี อัลกอริธึม make_heap , push_heapและpop_heapสำหรับฮีป (โดยปกติจะใช้ฮีปแบบไบนารี) ซึ่งทำงานกับตัววน ซ้ำแบบเข้าถึงแบบสุ่มใดๆ ก็ได้ โดยจะถือว่าตัววนซ้ำเหล่านั้นเป็นการอ้างอิงถึงอาร์เรย์ และใช้การแปลงอาร์เรย์เป็นฮีป นอกจากนี้ยังมีคลาสstd::priority_queueซึ่งห่อหุ้มฟังก์ชันเหล่านี้ไว้ในคลาสที่คล้ายกับคอนเทนเนอร์ อย่างไรก็ตาม ยังไม่มีการสนับสนุนมาตรฐานสำหรับการดำเนินการแทนที่, เลื่อนขึ้น/เลื่อนลง หรือลด/เพิ่มคีย์
ไลบรารีBoost C++ประกอบด้วยไลบรารีฮีป ซึ่งแตกต่างจาก STL ตรงที่รองรับการดำเนินการลดและเพิ่ม และรองรับฮีปประเภทเพิ่มเติม ได้แก่ ฮีปแบบd -ary, binomial, Fibonacci, pairing และ skew heap
มีไลบรารีสำหรับการจัดการฮีปแบบทั่วไปสำหรับภาษา CและC++ซึ่ง รองรับทั้ง ฮีปแบบ D-aryและฮีปแบบ Bโดยมี API ที่คล้ายกับ STL
ไลบรารีมาตรฐานของภาษาโปรแกรม Dประกอบด้วยstd.container.BinaryHeap ซึ่งถูกนำไปใช้ในรูปแบบของ ช่วง (range)ของ D สามารถสร้างอินสแตนซ์ได้จากช่วงใดๆ ที่เข้าถึงได้แบบสุ่ม BinaryHeap มีอินเทอร์เฟซช่วงอินพุต ที่อนุญาตให้วนซ้ำด้วยคำสั่ง foreachในตัวของ D และบูรณาการกับ API แบบช่วงของแพ็กเกจstd.algorithm
สำหรับภาษา Haskellมี โมดูล Data.Heapครับ
แพลตฟอร์มJava (ตั้งแต่เวอร์ชัน 1.5) มีการใช้งานฮีปแบบไบนารีโดยใช้คลาสjava.util.PriorityQueueในJava Collections Frameworkคลาสนี้จะใช้งาน min-heap เป็นค่าเริ่มต้น หากต้องการใช้งาน max-heap โปรแกรมเมอร์ต้องเขียนตัวเปรียบเทียบแบบกำหนดเอง ไม่มีการรองรับการดำเนินการแทนที่ เลื่อนขึ้น/เลื่อนลง หรือลด/เพิ่มคีย์
Pythonมี โมดูล heapqที่ใช้โครงสร้างข้อมูลแบบไบนารีฮีปเพื่อสร้างคิวลำดับความสำคัญ ไลบรารีนี้ยังมีฟังก์ชัน heapreplace เพื่อรองรับการรวมข้อมูลแบบ k-way อีกด้วย
PHPมีทั้ง max-heap ( SplMaxHeap ) และ min-heap ( SplMinHeap ) ในไลบรารีมาตรฐานของ PHP ตั้งแต่เวอร์ชัน 5.3 เป็นต้นไป
Perl มีการใช้งานฮีปแบบไบนารี ฮี ปแบบทวินาม และฮีปแบบฟิโบนาชชี ใน ชุดการแจกจ่าย Heapที่มีให้ใช้งานบนCPAN
ภาษาGoมี แพ็ก เกจ heapที่รวบรวมอัลกอริธึมเกี่ยวกับ heap ซึ่งทำงานกับชนิดข้อมูลใดๆ ก็ได้ที่ตรงตามอินเทอร์เฟซที่กำหนดไว้ แพ็กเกจนี้ไม่รองรับการดำเนินการ replace, sift-up/sift-down หรือ decrease/increase-key
ไลบรารีCore Foundationของ Apple มี โครงสร้างCFBinaryHeap อยู่
Pharoมีการใช้งานโครงสร้างข้อมูลแบบฮีป (heap) ในแพ็คเกจ Collections-Sequenceable พร้อมด้วยชุดกรณีทดสอบ โดยฮีปถูกนำมาใช้ในการทำงานของลูปเหตุการณ์ตัวจับเวลา (timer event loop)
ภาษา โปรแกรม Rustมีการใช้งาน max-heap แบบไบนารีที่เรียกว่าBinaryHeapซึ่งอยู่ใน โมดูล collectionsของไลบรารีมาตรฐาน
.NETมี คลาส PriorityQueueซึ่งใช้การใช้งาน min-heap แบบควอเทอร์นารี (d-ary) โดยมีให้ใช้งานตั้งแต่ .NET 6 เป็นต้นไป

ดูเพิ่มเติม

อัลกอริทึมการเรียงลำดับ
โครงสร้างข้อมูลการค้นหา
Treapคือรูปแบบหนึ่งของต้นไม้ค้นหาแบบไบนารีโดยอิงจากต้นไม้เรียงลำดับแบบฮีป

ลิงก์ภายนอก

ฮีปที่ Wolfram MathWorld
คำอธิบายเกี่ยวกับวิธีการทำงานของอัลกอริธึมฮีปพื้นฐาน
เบนท์ลีย์, จอน หลุยส์ (2000). เคล็ดลับการเขียนโปรแกรม ( ฉบับที่ 2). แอดดิสัน เวสลีย์. หน้า147–162 . ISBN 0201657880.

[8] การแทรกแต่ละครั้งใช้เวลา O(log( k )) ในขนาดฮีปที่มีอยู่ ดังนั้น $\sum _{k=1}^{n}O(\log k)$ . เนื่องจาก $\log n/2=(\log n)-1$ โดยที่ค่าคงที่ (ครึ่งหนึ่ง) ของการแทรกเหล่านี้จะอยู่ภายในค่าคงที่จากค่าสูงสุด ดังนั้นในเชิงอนุกรมวิธานเราสามารถสมมติได้ว่า $k=n$ อย่างเป็นทางการแล้ว เวลาคือ $nO(\log n)-O(n)=O(n\log n)$ สิ่งนี้สามารถเห็นได้ชัดเจนจากค่าประมาณของสเตอร์ลิง เช่น กัน

[13] การสร้างฮีป (make-heap)คือการดำเนินการสร้างฮีปจากลำดับของ องค์ประกอบที่ไม่เรียงลำดับจำนวน nรายการ สามารถทำได้ใน เวลา Θ ( n ) เมื่อใดก็ตามที่ meldทำงานใน เวลา O (log n ) (โดยที่ความซับซ้อนทั้งสองสามารถเฉลี่ยได้)^[⁹^]^[¹⁰^]อัลกอริทึมอื่นบรรลุ Θ ( n ) สำหรับฮีปไบนารี^[¹¹^]

[bootstrap-meld-15] 1 2 3สำหรับ ฮีป แบบถาวร (ที่ไม่รองรับการเพิ่มคีย์ ) การแปลงทั่วไปจะลดต้นทุนของการรวมให้เท่ากับต้นทุนของการแทรกในขณะที่ต้นทุนใหม่ของการลบสูงสุดคือผลรวมของต้นทุนเดิมของการลบสูงสุดและการรวม^{[ 14 ]}ในที่นี้ จะทำให้การรวมทำงานใน เวลา Θ (1) (เฉลี่ย หากต้นทุนของการแทรกคือ) ในขณะที่การลบสูงสุดยังคงทำงานใน O (log n ) เมื่อนำไปใช้กับฮีปแบบไบโนเมียลแบบเฉียง จะได้คิว Brodal-Okasaki ซึ่งเป็นฮีปแบบถาวรที่มีความซับซ้อนในกรณีที่เลวร้ายที่สุดที่เหมาะสมที่สุด^[¹³^]

[pairingdecreasekey-22] ขอบล่างของ $\Omega (\log \log n),$ ^{[ 17 ]}ขอบเขตบนของ $O(2^{2{\sqrt {\log \log n}}}).$ ^{[ 18 ]}

[optimum-26] 1 2คิว Brodal และฮีป Fibonacci แบบเข้มงวดบรรลุความซับซ้อนในกรณีที่เลวร้ายที่สุดที่เหมาะสมที่สุดสำหรับฮีป โดยโครงสร้างเหล่านี้ได้รับการอธิบายครั้งแรกว่าเป็นโครงสร้างข้อมูลเชิงคำสั่ง คิว Brodal-Okasaki เป็น โครงสร้างข้อมูล ถาวรที่บรรลุความเหมาะสมที่สุดเช่นเดียวกัน ยกเว้นว่าไม่รองรับการเพิ่มคีย์

[

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

7

[ a ]

[ 8 ]

[ข]

[ 9 ]

[ 10 ]

[ 12 ]

[

[ 13 ]

[ 15 ]

[ 16 ]

[

[ 19 ]

[ 20 ]

[ 21 ]

[ e ]

[ 22 ]

[ 23 ]

[

[ 14 ]

[ 17 ]

[ 18 ]

[ 24 ]