กลับไปหน้าบทความ

อ่าน 1 นาที

ฮีปที่สามารถระบุตำแหน่งได้

ใน วิทยาการคอมพิวเตอร์ ฮี ปที่สามารถเข้าถึงได้ (addressable heap) เป็น ชนิดข้อมูลนามธรรม โดยเฉพาะอย่างยิ่ง มันคือ ฮีปที่สามารถผสานได้ (mergeable heap)...

ฮีปที่สามารถระบุตำแหน่งได้

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

คำนิยาม

ฮีปที่สามารถระบุที่อยู่ได้รองรับการดำเนินการต่อไปนี้: [ 1 ]

  • Make-Heap()ทำให้เกิดกองขยะว่างเปล่า
  • Insert(H,x)โดยการแทรกองค์ประกอบxลงในฮีปHและส่งคืนค่าแฮนเดิลให้กับองค์ประกอบนั้น
  • Min(H)โดยส่งคืนตัวชี้ไปยังองค์ประกอบที่เล็กที่สุด หรือNilหากไม่มีองค์ประกอบดังกล่าวอยู่ ก็จะส่งคืนค่าอื่น
  • Extract-Min(H)โดยดึงและส่งคืนตัวชี้ไปยังองค์ประกอบที่เล็กที่สุด หรือNilหากไม่มีองค์ประกอบดังกล่าวอยู่
  • Remove(h)โดยการลบองค์ประกอบที่อ้างอิงโดยh(ออกจากฮีปที่เกี่ยวข้อง)
  • Decrease-Key(h,k)ลดค่าคีย์ขององค์ประกอบที่อ้างอิงลงhเหลือk; ผิดกฎหมายหากkค่ามากกว่าค่าคีย์ที่hอ้างอิง
  • Merge(H1,H2)โดยการรวมองค์ประกอบของH1และ เข้าด้วย H2กัน

ตัวอย่าง

ตัวอย่างของฮีปที่สามารถระบุตำแหน่งได้ ได้แก่:

สามารถดูรายชื่อที่ครบถ้วนยิ่งขึ้นพร้อมการเปรียบเทียบประสิทธิภาพได้ที่นี่

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ฮีปที่สามารถระบุตำแหน่งได้

ใน วิทยาการคอมพิวเตอร์ ฮี ปที่สามารถเข้าถึงได้ (addressable heap) เป็น ชนิดข้อมูลนามธรรม โดยเฉพาะอย่างยิ่ง มันคือ ฮีปที่สามารถผสานได้ (mergeable heap)...

คำนิยาม

ฮีปที่สามารถระบุที่อยู่ได้รองรับการดำเนินการต่อไปนี้: [ 1 ]

ตัวอย่าง

ตัวอย่างของฮีปที่สามารถระบุตำแหน่งได้ ได้แก่: