ฮีพ (Heap)
โครง สร้างข้อมูลแบบฮีพ (Heap) เป็นโครงสร้างข้อมูลแบบพิเศษของไบนารีทรีที่มีคุณสมบัติไบนารีทรีแบบสมบูรณ์ ซึ่งค่าของโหนดรากจะมากกว่าหรือเท่ากับค่าของโหนดลูกเสมอ
คุณ สมบัติของไบนารี่ทรี
· แต่ ละ Subtree ค่าของ root >= child เสมอ
· Max heap
· หรือ แต่ละ subtree ค่าของ root <= child เสมอ
· Min heap
· เป็น complete หรือ nearly complete
· leaf ทุกโหนด จะอยู่ level เดียวกัน
· ถ้า ไม่ complete,leaf จะเรียงอยู่ทางด้านซ้ายมือ
โครง สร้างของ Max Heap
โครง สร้างของ Mix Heap
Heap Operation
1. Insert & Reheap up
· insert โหนดใหม่ที่ level ล่างสุด ณ ตำแหน่งว่างด้านซ้ายสุด
· reheap up ปรับ tree หลังจาก insert ให้เป็น heap
2. Delete & Reheap down
· delete ที่ root เท่านั้นและนำ node ที่ level ล่างสุดตำแหน่งขวาสุดขึ้นมาแทน
· reheap down ปรับ tree หลังจาก delete ให้เป็น heap
Reheap up
· สลับที่ระหว่างโหนดที่ insert เข้ามากับ parent ของมันเองตามหลักของ heap
· ทำซ้ำกับโหนดเดิมจนกว่าจะอยู่ ตำแหน่งที่ถูกต้อง
Reheap down
· สลับที่ระหว่างโหนดที่ตำแหน่ง root กับโหนดลูกของมันเองจนกว่าโหนดนั้นจะอยู่ตำแหน่งที่ถูกต้อง
· ทำซ้ำจนกว่า root จะอยู่ตำแหน่งที่ถูกต้อง
การ แทน heap ในหน่วยความจำ
· นิยมแทน heap ลงในอาร์เรย์ 1 มิติ เนื่องจากคุณสมบัติของการเป็น nearly complete ของตัวมันเอง
· ข้อมูลที่จัดเก็บลงในอาร์เรย์ จะเรียงต่อกันไปตามลำดับจากซ้ายไปขวาของ แต่ละ level ใน heap
· จะได้ความสัมพันธ์ของตำแหน่ง ข้อมูลใน heap คือ
– parent ของโหนด i ใดๆ = i/2 ถ้า i <> 1 (โหนดรูทอยู่ที่ตำแหน่งแรกของอาร์เรย์)
– left child ของโหนด i ใดๆ = 2i (โหนดลูกซ้ายจะอยู่ที่ 2 เท่าของโหนดพ่อ)
– right child ของโหนด i ใดๆ = 2i + 1(โหนดลูกขวาอยู่ที่ตำแหน่ง 2 เท่าบวก 1)
