Improve company productivity with a Business Account.Sign Up

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 867
  • Last Modified:

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(){
    }
}
0
bigmdawg
Asked:
bigmdawg
2 Solutions
 
ADSLMarkCommented:
A very well explaining website can be found here:

http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/heap/heapen.htm

On the bottom there is even an implementation in Java.

Mark
0
 
hoomanvCommented:
Naturally you don't need to implement Heap because java 1.5 already has one
java.util.PriorityQueue
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Get your problem seen by more experts

Be seen. Boost your question’s priority for more expert views and faster solutions

Tackle projects and never again get stuck behind a technical roadblock.
Join Now