Removing the Min Element from Deaps (การลบค่าต่ำสุดจากดีป)

Deap Deletion Algorithm

เป้าหมาย: ลบ Minimal Value จาก Deap
Height = O(log n) → Time = O(log n)

Procedure: deap_deletion(b[], m)

Procedure deap_deletion(b[], m):
    if (m < 2) return;           // No elements
    min = b[2];                  // Save minimum value (Root of Min Heap)

    for (i = 2; 2*i <= m; b[i] = b[k], i = k) {
        k = i * 2;               // Left child
        if (k+1 <= m && b[k] > b[k+1])  // Choose smaller child
            k++;
    }
    k = max_value(i);            // Corresponding node in Max Heap
    if (x > b[k]) {
        b[i] = b[k];
        insert y into maximum subtree;
    } else {
        insert y into minimum subtree;
    }

Explanation

1. Min Element อยู่ที่ b[2] (Root ของ Min Heap)
2. Percolate Down ใน Min Heap: เลือก Child ที่เล็กกว่า (Standard Heap Delete)
3. เมื่อถึง Leaf ของ Min Heap → หา Corresponding Node ใน Max Heap (max_value)
4. Compare กับ Last Element (y) → Insert กลับเข้า Min หรือ Max Subtree ตามเงื่อนไข
5. Maintain Deap Property: Min Heap Keys ≤ Corresponding Max Heap Keys

สรุป

Deap Deletion = Min Heap Delete + Corresponding Max Heap Adjustment
O(log n) Time, Maintains Deap Invariant