Question

Please show work. Thank you for your help.

7. (10 pts) First, give in pseudocode a procedure DELETE(A, i) that deletes Ali] from max binary heap A that currently has n elements. Then analyze carefully the time complexity of your algorithm. Note: If it is easier to assume that the binary heap is stored in A[1..n) you may do this. Just indicate if you are assuming that the array is stored in A[1..n) or Afo..n-1). Hint: Use ideas from the algorithm for removing the maximum from a binary hep.

Answer 1

Let us assume the array A to be of the form A[0,1,....,n-1]. A maximum binary heap is a complete binary tree in which each parent is greater than its children. A complete binary tree is a binary tree in which each level, except possibly the last level, is completely filled and all the nodes are as left as possible.

While doing insertion or deletion in a binary tree we need to maintain the heap property.

In binary heap we represent a tree using an array. If the index of the parent node in the array is 'i' then the index of its children in the array will be '2*i+1' and '2*i+2'. If the index of the child node in the array is 'i' then the index of its parent in the array will be '(i-1)/2'. We will be using these rules to calculate the parent index from child index and vice versa.

It is difficult to delete an element from the tree which has children(1 or 2). On the other hand, it is really easy to delete an element with no children.

We have to delete the i^th element from the array. This element can have no child, one child or two children. So we do not know the no. of children this element will have. So we swap this element with the last element in the array as the last element is always a leaf node. Then we delete this element on the last position by reducing the size of the array and find the correct position for the element which is now in the i^th position by comparing it with its parent node. If it is greater than its parent then it is swapped. Now we compare the new position of the element in the array with its children. If it is smaller than its children then it is swapped.So we first find the correct position of the array in the upward direction then we move all the way down in the tree.

Let n be a global element which maintains the size of the heap. Whenever DELETE function is called n is reduced by and whenever INSERT function is called n is incremented by 1.

DELETE(A,i) //function name

int temp1 = A[i]; // temp1 stores the element to be deleted
int temp2 = A[n-1]; // temp2 stores the last element in the array

swap(temp1, temp2); // values of temp1 and temp2 are swapped

int childIndex = i; // now the element which is on the position acts as the parent and we need to compare it with its children

int parentIndex = (childIndex-1)/2;

while(childIndex!=0 && A[parentIndex]<A[childIndex]) {
int temp = A[parentIndex];
A[parentIndex] = A[childIndex];
A[childIndex] = temp;
childIndex = parentIndex;
parentIndex = (childIndex-1)/2;
}

int parent =childIndex; //now this child element acts as parent element and its compared with its children

while(parent<n) {
              
               int child1 = 2*parent+1;
               int child2 = 2*parent+2;
              
               int p = A[parent];
              
               int c1 = Integer.MAX_VALUE;
               int c2 = Integer.MAX_VALUE;
              
               if(child1<n) {
                   c1 = A[child1];
               }
               if(child2<n) {
                   c2 = A[child2];
               }
              
               if(p>c1 && p>c2) {
                   break;
               }
               else if(p>c1) {
A[child2] = p;
A[parent] = c2;
                   parent = c2;
               }
               else if(p>c2) {
A[child1] = p;
A[parent] = c1;
                   parent = c1;
               }
               else {
                   if(c1>c2) {
A[child1] = p;
A[parent] = c1;
                       parent = c1;
                   }
                   else {
A[child2] = p;
A[parent] = c2;
                       parent = c2;
                   }
               }

}

n--; // element has been deleted so size of array reduces by 1

}

Now we have got the array in the correct form and we just need to delete the last element. We can simply make a global size element n and subtract 1 from it whenever delete function is called

The time complexity of the algorithm is O(h) , where h is the height of the tree as the comparisons are happening between parent and child nodes (which are on different levels in the tree). The height of a complete binary tree is h = [ceil(log₂(n+1))-1] . So the time complexity of the algorithm is O(log₂n).