สารบัญ:
คำจำกัดความ - Heap หมายถึงอะไร
ฮีปในบริบทของโครงสร้างข้อมูลเป็นโครงสร้างข้อมูลแบบทรีที่ตอบสนองคุณสมบัติฮีพโดยที่แต่ละอิลิเมนต์ถูกกำหนดค่าคีย์หรือการให้น้ำหนัก คีย์ค่าที่ต่ำกว่าจะมีโหนดพาเรนต์พร้อมกับคีย์ที่มีค่าสูงกว่าเสมอ สิ่งนี้เรียกว่าโครงสร้าง max-heap และในบรรดาโหนดทั้งหมดโหนดรูทจะมีคีย์สูงสุด
บางครั้งโครงสร้างแบบทรีมีกฎโครงสร้างแบบผกผันซึ่งองค์ประกอบที่มีคีย์ค่าที่สูงกว่าจะมีคีย์ค่าที่ต่ำกว่าเสมอเป็นโหนดพาเรนต์ สิ่งนี้เรียกว่าโครงสร้าง min-heap และในบรรดาโหนดทั้งหมดโหนดรูทมีคีย์ต่ำสุด
Techopedia อธิบายกอง
ไม่มีข้อ จำกัด ในทางปฏิบัติเกี่ยวกับจำนวนลูกแต่ละโหนดที่สามารถมีได้ในฮีปแม้ว่าแต่ละโหนดจะมีสองโหนดมากที่สุด ฮีปถือเป็นการใช้งานที่มีประสิทธิภาพสูงสุดของชนิดข้อมูลนามธรรมหรือที่เรียกว่าคิวลำดับความสำคัญ การนำฮีปไปใช้เป็นสิ่งจำเป็นในอัลกอริธึมกราฟต่างๆ (รวมถึงอัลกอริธึมของ Dijkstra) เช่นเดียวกับอัลกอริทึมการเรียงลำดับฮีปพอร์ต
Heaps มีความแปรปรวนหลายอย่างที่ทำหน้าที่เป็นคิวลำดับความสำคัญของประเภทข้อมูลนามธรรมที่มีประสิทธิภาพสูง แอปพลิเคชันจำนวนมากเช่นอัลกอริธึมกราฟจำเป็นต้องมีการใช้คิวลำดับความสำคัญ
อาเรย์เป็นรูปแบบการนำฮีปส่วนใหญ่ไปใช้โดยไม่จำเป็นต้องมีพอยน์เตอร์เชื่อมโยงระหว่างองค์ประกอบ
กองดำเนินการหลายอย่างรวมไปถึง:
- Find-max: ค้นหาโหนดคีย์สูงสุดในกลุ่มของโหนด
- Find-min: ค้นหาโหนดคีย์ต่ำสุดในกลุ่มของโหนด
- Delete-max: ลบโหนดคีย์สูงสุดในกลุ่มของโหนด
- Delete-min: ลบโหนดคีย์ต่ำสุดในกลุ่มของโหนด
ฮีปประกอบด้วยฟังก์ชันที่ทำการผสานการแทรกและการเปลี่ยนแปลงที่สำคัญ
คำจำกัดความนี้ถูกเขียนในบริบทของโครงสร้างข้อมูล
