- #1

DODGEVIPER13

- 672

- 0

(Heap visualization) Write a Java applet that displays a heap graphically, as

shown in Figure 24.7. The applet let's you insert and delete an element from the

heap.

public class MinHeap<E extends Comparable>{

private java.util.ArrayList<E> list = new java.util.ArrayList<E>();

public MinHeap(){

}

public MinHeap(E[] objects){

for (int i = 0; i < objects.length; i++)

add(objects

*);*

}

public void add(E newObject){

list.add(newObject);

int currentindex = list.size() - 1;

while (currentindex > 0){

int parentIndex = (currentindex-1)/2;

E p = list.get(parentIndex);

if (newObject.compareTo(p) >= 0){

break;

}

list.set(currentindex, p);

currentindex = parentIndex;

}

list.set(currentindex, newObject);

}

public E remove(){

if(list.size() == 0) return null;

E removedobject = list.get(0);

list.set(0, list.get(list.size() - 1));

list.remove(list.size() - 1);

int currentindex = 0;

while(currentindex < list.size()){

int left = 2*currentindex+1;

int right = 2*currentindex+2;

if(left >= list.size()) break;

int max = left;

if(right < list.size()){

if(list.get(max).compareTo(list.get(right)) < 0){

max=right;

}

}

if (list.get(currentindex).compareTo(list.get(max)) < 0){

E temp = list.get(max);

list.set(max, list.get(currentindex));

list.set(currentindex, temp);

currentindex = max;

}

else

break;

}

return removedobject;

}

public int getSize(){

return list.size();

}

}

}

public void add(E newObject){

list.add(newObject);

int currentindex = list.size() - 1;

while (currentindex > 0){

int parentIndex = (currentindex-1)/2;

E p = list.get(parentIndex);

if (newObject.compareTo(p) >= 0){

break;

}

list.set(currentindex, p);

currentindex = parentIndex;

}

list.set(currentindex, newObject);

}

public E remove(){

if(list.size() == 0) return null;

E removedobject = list.get(0);

list.set(0, list.get(list.size() - 1));

list.remove(list.size() - 1);

int currentindex = 0;

while(currentindex < list.size()){

int left = 2*currentindex+1;

int right = 2*currentindex+2;

if(left >= list.size()) break;

int max = left;

if(right < list.size()){

if(list.get(max).compareTo(list.get(right)) < 0){

max=right;

}

}

if (list.get(currentindex).compareTo(list.get(max)) < 0){

E temp = list.get(max);

list.set(max, list.get(currentindex));

list.set(currentindex, temp);

currentindex = max;

}

else

break;

}

return removedobject;

}

public int getSize(){

return list.size();

}

}