12.2. In the heap. java program the insert() method inserts a new node in the he

Question

12.2. In the heap. java program the insert() method inserts a new node in the heap and ensures the heap condition is preserved. Write a toss () method that places a new node in the heap array without attempting to maintain the heap condi- tion. (Perhaps each new item can simply be placed at the end of the array.) Then write a restoreHeap() method that restores the heap condition through- out the entire heap. Using toss(o) repeatedly followed by a single restoreHeap() is more efficient than using insert() repeatedly when a large amount of data must be inserted at one time. See the description of heapsort for clues. To test your program, insert a few items, toss in some more, and then restore the heap.

Explanation / Answer

//The following methods are given here. The student can verify this

import java.io.*;

import java.util.*;

class Node

{

int val;

private Node(int key)

{ val = key; }

public int gettingKey()

{ return val; }

public void settingKey(int value)

{ val = value; }

class Heap

{

Node[] heap;

int maximumSize;

int presentSize;

public Heap(int max)   

{

maximumSize = max;

presentSize = 0;

heap = new Node[maximumSize];  

}

public boolean arrayEmpty()

{ return presentSize==0; }

public int getpresentSize()

{ return presentSize++; }

public boolean insert(int key)

{

if(presentSize==maximumSize)

return false;

Node n = new Node(key);

heap[presentSize] = n;

return true;

}

public boolean toss(int key)

{

if(presentSize==maximumSize)

return false;

Node n = new Node(key);

heap[presentSize] = n;

presentSize++;

return true;

}  

public void restoreHeap(int index)

{

int left = (index * 2) + 1; //array starts with 0.Hence +1 is added

int right = left +1;

int big = index;

if(left < presentSize && heap[left].gettingKey() > heap[index].gettingKey())

big = left; //The left is bigger

if(right < presentSize && heap[right].gettingKey() > heap[big].gettingKey())

big = right; //Right is large when compared to left and index

if(big != index) //If a swap is necessary

{

//Swap

Node swap = heap[big];

heap[big] = heap[index];

heap[index] = swap;

restoreHeap(big);

}

}

public void main(String[] args)

{

Scanner sca=new Scanner(System.in);

int value, value2;

Heap h = new Heap(31);  

boolean s;

h.insert(5);

h.insert(4);

h.insert(9);

h.insert(8);

h.insert(6);

while(true)

{

System.out.print("Enter first letter of ");

System.out.print(" insert, toss, 'e' for restore: ");

String ch = sca.next();

if(ch=="i") { // insert

System.out.print("Enter value to insert: ");

s = h.insert(value);

if( !s )

System.out.println("Can't insert; heap full");}

  

else if(ch=="t"){ // insert

System.out.print("Enter value to toss: ");

//value = getInt();

s = h.toss(value);

if( !s )

System.out.println("Can't toss; heap full");}

else{

h.restoreHeap(h.getpresentSize());

  

} }

}}

  

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.