Chèn phần tử vào Deaps

Để chèn phần tử vào cấu trúc dữ liệu deap, có thể cần thủ tục tính giá trị nhỏ nhất và lớn nhất như mô tả dưới đây:

Procedure min_value(m): // Tính giá trị nhỏ nhất trong deap. return m - 2^log₂(m-1) ;

Procedure max_value(m): // Tính giá trị lớn nhất trong deap. return m + 2^log₂(m-1) ;

Thao tác chèn trong deap có thể thực hiện theo cách sau:

• Đối với heap b[], kiểm tra m có phải vị trí trong max-heap của deap không.
• Tính giá trị min và max trong deap.
• So sánh giá trị khóa tại cây con trái và cây con phải.
• Cuối cùng, thực hiện chèn với thuật toán sau.

Procedure deap_insertion(b[], y, m):
    if (m == 1)
        b[2] = y;
    else {
        if (m is in maximum subtree) {
            index = min_value(m);
            if (y < b[index]) {
                b[m] = b[index];
                insert y in minimum subtree;
            } else
                insert y in maximum subtree;
        } else {
            index = max_value(m);
            if (x > b[index]) {
                b[m] = b[index];
                insert y into maximum subtree;
            } else
                insert y into minimum subtree;
        }
    }