Link to home
Start Free TrialLog in
Avatar of bigmdawg
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(al.get(child))>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).compareTo(al.get(rightChild))>0)
                minChild=rightChild;
            if(al.get(parent).compareTo(al.get(minChild))>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(){
    }
}
SOLUTION
Avatar of ADSLMark
ADSLMark

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of hoomanv
Naturally you don't need to implement Heap because java 1.5 already has one
java.util.PriorityQueue
ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial