ฮีปที่สามารถระบุตำแหน่งได้
ในวิทยาการคอมพิวเตอร์ฮีปที่สามารถเข้าถึงได้ (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กัน
ตัวอย่าง
ตัวอย่างของฮีปที่สามารถระบุตำแหน่งได้ ได้แก่:
สามารถดูรายชื่อที่ครบถ้วนยิ่งขึ้นพร้อมการเปรียบเทียบประสิทธิภาพได้ที่นี่