Inserting an Element into Deaps

To insert element into deap data structure, we might need the procedures to calculate the minimum and maximum values as depicted below −

Procedure min_value(m): //To calculate the minimum value in deap. return m-2^log₂(^(m-1) ;

Procedure max_value(m): //To calculate the maximum value in deap. return m+2^log₂^(m-1);

The insertion operation in deap data structure can be done in following way −

• For any heap b[], we should check if m is a position within the maximum-heap of deap.
• We shall then calculate the minimum and maximum values in deap.
• Now, comparison is done between the key values at left sub-tree and right sub-tree.
• At last, we perform the insertion operation with following Algorithm.

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; }