Question

Write PSEUDO CODE! for Min_Heap_Delete(A,i) which deletes the item at position i in Min_Heap A. Assume that A is a one-dimensional array. Hint:Think about “bubbling up” and “bubbling down” and the operations that do these, then give the best upper bound you can on the worst case running time of your method, in ordered notations.

Answer 1

JAVA CODE:

import java.util.*;
import java.io.*;

public class Main {

public static void main(String[] args) throws IOException {

Scanner sc = new Scanner(System.in);
System.out.println("Enter t:");
int t=sc.nextInt();

while(t-->0) {
System.out.println("Enter n and k:");
int n = sc.nextInt();

int k = sc.nextInt();

Min_Heap Min_Heap = new Min_Heap(n);
System.out.println("Enter n values to insert_into_Heap into heap:");
for (int i = 0; i < n; i++) {

Min_Heap.insert_into_Heap(sc.nextInt());

}

Min_Heap.Min_Heap_Delete(k);

Min_Heap.print_the_Heap(sc);

System.out.println();

}

}

}

class Min_Heap

{

private int[]Heap;

private int size;

private int maxSize;

private static final int FRONT = 1;

Min_Heap(int maxSize)

{

this.maxSize = maxSize;

size=0;

Heap = new int[this.maxSize+1];

Heap[0] = Integer.MIN_VALUE;

}

private int parent_Node(int position) {

return position / 2;

}

private int left_Child(int position)

{

return (2*position);

}

private int right_Child(int position)

{

return (2*position)+1;

}

private boolean Is_Leaf(int position)

{

if(position>=(size/2) && position<=size)

return true;

return false;

}

private void Swap(int fposition, int sposition)

{

int temp;

temp = Heap[fposition];

Heap[fposition]=Heap[sposition];

Heap[sposition]=temp;

}

private void Min_Heapify(int position)

{

int left = left_Child(position);

int right = right_Child(position);

int largest = position;

if(left<=size && Heap[left]<Heap[largest])

largest=left;

if(right<=size && Heap[right]<Heap[largest])

largest = right;

if(largest!=position)

{

Swap(position, largest);

Min_Heapify(largest);

}

}

void insert_into_Heap(int data)

{

if(size>=maxSize)

return;

Heap[++size]=data;

int i=size;

while(Heap[i]<Heap[parent_Node(i)])

{

Swap(i,parent_Node(i));

i=parent_Node(i);

}

}

private void build_Heap()

{

int j=(int)Math.floor(size/2.0);

for(int i=j;i>=1;i--){

Min_Heapify(i);

}

}

public void heap_Sort(Writer wr) throws IOException {

build_Heap();

int length=size;

for(int i=size;i>=2;i--)

{

Swap(1,i);

size--;

Min_Heapify(1);

}

size=length;

// print_the_Heap(wr);

}

public int Remove()

{

int popped = Heap[FRONT];

Heap[FRONT] = Heap[size];

size=size-1;

Min_Heapify(FRONT);

return popped;

}

public void Min_Heap_Delete(int i)

{

decrease_Key(i, Integer.MIN_VALUE);

Remove();

}

private void decrease_Key(int i, int new_val) {

Heap[i]=new_val;

while(i !=0 && Heap[parent_Node(i)]>Heap[i])

{

Swap(i,parent_Node(i));

i=parent_Node(i);

}

}
//Min_Heap_Delete
void print_the_Heap(Scanner sc) throws IOException {
System.out.println("The output after deleting the k-th index from heap will be: ");

for(int i=1;i<=size;i++)

{

//wr.write(Heap[i]+" ");

System.out.print(Heap[i]+" ");

}

}

}

OUTPUT SCREENSHOT:

Here I have given the inputs as:

t=1

n =5 and k=4

and the values inserted were

1 2 3 4 5

So since k is 4 will be deleted from the heap as you can see the output.

Hope you like the code and don't forget to give UPVOTE as it means a lot..THANKS:)