ฮีป
จากวิกิพีเดีย สารานุกรมเสรี
| ฮีป | |
|---|---|
 รูปแบบการเรียงตัวของฮีป โดยสมาชิกที่สำคัญกว่า (ในที่นี้เป็นฮีปมากสุดคือเลขที่มีค่ามากจะสำคัญ) จะอยู่ด้านบน |
|
| ความสำคัญของลำดับ | FIFO (First In First Out) แต่เรียงตามลำดับความสำคัญ |
| การซ้ำกันของสมาชิก | อนุญาตให้ซ้ำกันได้ |
| เวลาที่ใช้ค้นหาตามดัชนี | |
| เวลาที่ใช้ค้นหาตามค่า | |
| เวลาที่ใช้ในการเข้าถึง | O(log n) |
| การทำให้ว่าง | ทำให้ทุกตัวเป็น null |
| เวลาที่ใช้ทำให้ว่าง | O(n) |
| โครงสร้างต้นแบบ | |
| โครงสร้างที่นำไปใช้ | |
ฮีป(heap) เป็นโครงสร้างข้อมูลที่นำมาสร้างคิวลำดับความสำคัญ (implementation) รูปแบบหนึ่ง ซึ่งนิยมใช้กันมาก โดยการสร้างแนวคิดรูปแบบต้นไม้ โดยให้มีความสัมพันธ์เป็นปมพ่อมีลำดับความสำคัญมากกว่าปมลูก
แนวคิดของฮีปนอกจากนำมาสร้างคิวลำดับความสำคัญแล้ว ยังนำมาประยุกต์ใช้ในการสร้างโครงสร้างข้อมูลอื่นๆ เช่นทรีพ เป็นต้น
เนื้อหา |
[แก้] ลักษณะของฮีป
ฮีปเป็นต้นไม้ประเภทหนึ่งซึ่งจะจัดความสัมพันธ์ให้ปมพ่อ มีความสำคัญ(priority)มากกว่าปมลูก
[แก้] ฮีปรูปแบบต่างๆ
- ฮีปเติมเต็ม (completed heap) นอกจากที่จะเป็นฮีปแล้ว ยังเป็นต้นไม้เติมเต็ม(comleted tree)อีกด้วย ซึ่งฮีปประเภทนี้จะสามารถสร้างได้ด้วยแถวลำดับ
- ฮีปน้อยสุด (least heap) เป็นฮีปที่แทนความสำคัญด้วยตัวเลข โดยตัวเลขยิ่งน้อยจะยิ่งมีความสำคัญมาก เมื่อเขียนในรูปต้นไม้จะเหมือนว่าปมพ่อจะมีเลขความสำคัญน้อยกว่าปมลูกเสมอ
- ฮีปมากสุด (most heap) เป็นฮีปที่แทนความสำคัญด้วยตัวเลข โดยตัวเลขยิ่งมากจะยิ่งมีความสำคัญมาก เมื่อเขียนในรูปต้นไม้จะเหมือนว่าปมพ่อจะมีเลขความสำคัญมากกว่าปมลูก
- ทรีพ (treap) เป็นโครงสร้างข้อมูลที่สร้างข้อมูลเสริมให้มีความสัมพันธ์แบบฮีป ส่วนข้อมูลหลักจะเรียงความสัมพันธ์แบบต้นไม้ค้นหาแบบทวิภาค
[แก้] จุดเด่นของฮีป
ฮีปมีจุดเด่นในการเรียงลำดับในลักษณะต้นไม้ โดยเมื่อเรียงแล้วสมาชิกที่มีความสำคัญสูงสุดจะอยู่สูงสุดหรือเป็นราก ทำให้เข้าถึงข้อมูลที่มีความสำคัญสูงได้ง่าย อีกทั้งการเรียงแบบต้นไม้ โดยเฉพาะฮีปเติมเต็มด้วยแล้ว จึงสามารถลดเวลาการเข้าถึงลงเป็น O(log n)
[แก้] บริการที่มักจะมี
บริการนั้นจะเน้นบริการเดียวกับคิวลำดับความสำคัญ
- เพิ่มรายการแนบด้วยระดับไว้ในคิว (enqueue)
- ลบรายการที่มีความสำคัญสูงสุดและคืนค่านั้นกลับมา (prioritized dequeue)
- ดึงค่ารายการที่มีความสำคัญสูงสุดโดยไม่ลบรายการนั้นออก (peek)
[แก้] ความเร็วที่ใช้ในการทำงาน
จากการที่ฮีปเรียงตัวในลักษณะต้นไม้ โดยเฉพาะฮีปเติมเต็ม ทำให้ต้นไม้ที่ได้เป็นต้นไม้ประกันความสูง จึงเป็นการประกันการทำงานว่าอย่างมากจะใช้เวลา O(log n) และเข้าถึงข้อมูลที่สำคัญที่สุดได้ง่ายเพราะอยู่บนรากเป็นเวลาคงที่ O(1)
[แก้] ประเภทข้อมูลที่ใช้สร้างฮีป
เนื่องจากฮีปเป็นต้นไม้จึงอาจสร้างในลักษณะปมของต้นไม้ได้ ซึ่งใช้ประเภทข้อมูลประเภทโครงสร้าง หรือวัตถุ อย่างไรก็ตาม โดยปกติสำหรับการสร้างคิวลำดับความสำคัญเราจะสร้างแบบฮีปเติมเต็ม ซึ่งสามารถใช้ความสัมพันธ์ทางคณิตศาสตร์ ทำให้เราสามารถใช้แถวลำดับในการสร้างฮีปเติมเต็มได้
[แก้] ความสัมพันธ์ระหว่างดัชนีของปมพ่อและปมลูกในแถวลำดับของฮีปเติมเต็ม
เมื่อเราแวะผ่านฮีปเติมเต็มตามความกว้าง(bread-first search)และเรียงเป็นแถวลำดับแล้ว เราจะได้ความสำคัญที่ว่าสำหรับสมาชิกดัชนีที่ i ใดๆ
- ปมพ่อของสมาชิกตัวนี้อยู่ที่
- ปมลูกทั้งสองตัวของสมาชิกตัวนี้อยู่ที่ 2i + 1,2i + 2
[แก้] การสร้างบริการของฮีป
ในที่นี้กล่าวถึงลักษณะการทำงานของฮีปเติมเต็มในการทำคิวลำดับความสำคัญ สำหรับการทำงานของทรีพให้ดูทรีพ#การสร้างบริการของทรีพ
[แก้] การเข้าคิว
ทำได้โดยการเพิ่มสมาชิกไปที่หลังสุดของแถวลำดับก่อน และทำการสลับข้อมูลกับปมพ่อ(percolate up)เมื่อข้อมูลใหม่มีลำดับความสำคัญมากกว่า จนกระทั่งปมพ่อมีลำดับความสำคัญมากกว่าจึงหยุด
[แก้] การลบสมาชิกที่สำคัญที่สุด
ทำได้โดยการดึงเอาข้อมูลแรกสุดของแถวลำดับ กล่าวคือเป็นรากของฮีปเติมเต็ม ซึ่งจะมีลำดับความสำคัญมากที่สุดออก จากนั้นจะหยิบตัวสุดท้ายของแถวลำดับมาแทน (ซึ่งมักจะมีลำดับความสำคัญน้อย)และทำการลดลำดับลงโดยการสลับข้อมูลกับปมลูก(percolate down)จนข้อมูลสลับจนปมลูกมีลำดับความสำคัญน้อยกว่าจึงหยุด
[แก้] ดูเพิ่ม
|
|
|
|---|---|
| ประเภทข้อมูลอย่างย่อ | Collection • รายการ • เซต • ต้นไม้ • กองซ้อน • คิว • คิวสองหน้า • คิวลำดับความสำคัญ • Map |
| รายการ | รายการแถวลำดับ • รายการโยง |
| ต้นไม้ | ต้นไม้ค้นหาแบบทวิภาค • ทรีพ •ต้นไม้บาน • ต้นไม้แดงดำ • |
| คิว | คิว • คิวสองหน้า• คิวลำดับความสำคัญ • ฮีป |
| Map | ตารางแฮช |
| ดูเพิ่ม | ฟังก์ชันแฮช • ขั้นตอนวิธี • สัญกรณ์โอใหญ่ |
