Inserting an Element into Deaps (การแทรกข้อมูลในดีป)

Helper Procedures

Procedure min_value(m):  // Min Heap Position ของ Index m
    return m - 2^{log₂(m-1)};

Procedure max_value(m):  // Max Heap Position ของ Index m
    return m + 2^{log₂(m-1)};

Deap Insertion Algorithm

Procedure deap_insertion(b[], y, m):
    if (m == 1)
        b[2] = y;                    // First element
    else {
        if (m is in maximum subtree) {
            index = min_value(m);    // Corresponding min heap position
            if (y < b[index]) {
                b[m] = b[index];     // Swap with corresponding
                insert y in minimum subtree;
            } else
                insert y in maximum subtree;
        } else {                     // m in minimum subtree
            index = max_value(m);    // Corresponding max heap position
            if (y > b[index]) {
                b[m] = b[index];     // Swap with corresponding
                insert y into maximum subtree;
            } else
                insert y into minimum subtree;
        }
    }

Logic

1. Check m อยู่ Min หรือ Max Subtree
2. หา Corresponding Index ในอีก Subtree (min_value/max_value)
3. Compare y กับ Corresponding Element
4. ถ้า Violate Deap Property (Min > Max) → Swap และ Insert ในอีก Subtree
5. Else → Insert ใน Subtree เดิม

Deap Property

สำหรับ Corresponding Nodes a (Min), b (Max): a.key ≤ b.key เสมอ

สรุป

Deap Insertion = Navigate to Leaf + Possible Cross-Subtree Swap เพื่อ Maintain Invariant
O(log n) Time, ใช้ min_value/max_value Functions หา Corresponding Nodes