bigmdawg
asked on
Implementing a heapSort().
I built the heap and it works fine but I can't seem to get the sort to work right. Any help on getting started would be appreciated. Here's what I have so far.
import java.util.*;
public class Heap{
private ArrayList<Integer> al;
public Heap(){
al=new ArrayList<Integer>();
}
public Heap(ArrayList<Integer> al){
this.al=new ArrayList<Integer>(al);
}
public void insert(Integer obj){
al.add(obj);
int child=this.size()-1;
int parent=(child-1)/2;
while(parent>=0 && al.get(parent).compareTo(a l.get(chil d))>0){
Integer temp=al.get(child);
al.set(child, al.get(parent));
al.set(parent, temp);
child=parent;
parent=(child-1)/2;
}
}
public boolean isEmpty(){
return al.isEmpty();
}
public int size(){
return al.size();
}
public Integer delete(){
if(this.isEmpty())
return null;
if(this.size()==1)
return al.remove(0);
Integer min=al.get(0);
al.set(0, al.remove(this.size()-1));
int parent=0; //each parent may have 0, 1, 2 children
while(true){
int leftChild=(2*parent)+1;
int rightChild=leftChild+1;
if(leftChild>=this.size())
break;
int minChild=leftChild;
if(rightChild<this.size() && al.get(leftChild).compareT o(al.get(r ightChild) )>0)
minChild=rightChild;
if(al.get(parent).compareT o(al.get(m inChild))> 0){
Integer temp=al.get(parent);
al.set(parent, al.get(minChild));
al.set(minChild, temp);
parent=minChild;
}
else
break;
}
return min;
}
public void heapSort(){
}
}
import java.util.*;
public class Heap{
private ArrayList<Integer> al;
public Heap(){
al=new ArrayList<Integer>();
}
public Heap(ArrayList<Integer> al){
this.al=new ArrayList<Integer>(al);
}
public void insert(Integer obj){
al.add(obj);
int child=this.size()-1;
int parent=(child-1)/2;
while(parent>=0 && al.get(parent).compareTo(a
Integer temp=al.get(child);
al.set(child, al.get(parent));
al.set(parent, temp);
child=parent;
parent=(child-1)/2;
}
}
public boolean isEmpty(){
return al.isEmpty();
}
public int size(){
return al.size();
}
public Integer delete(){
if(this.isEmpty())
return null;
if(this.size()==1)
return al.remove(0);
Integer min=al.get(0);
al.set(0, al.remove(this.size()-1));
int parent=0; //each parent may have 0, 1, 2 children
while(true){
int leftChild=(2*parent)+1;
int rightChild=leftChild+1;
if(leftChild>=this.size())
break;
int minChild=leftChild;
if(rightChild<this.size() && al.get(leftChild).compareT
minChild=rightChild;
if(al.get(parent).compareT
Integer temp=al.get(parent);
al.set(parent, al.get(minChild));
al.set(minChild, temp);
parent=minChild;
}
else
break;
}
return min;
}
public void heapSort(){
}
}
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
java.util.PriorityQueue