Solved

Implementing a heapSort().

Posted on 2006-11-28
3
833 Views
Last Modified: 2013-11-23
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
Comment
Question by:bigmdawg
3 Comments
 
LVL 10

Assisted Solution

by:ADSLMark
ADSLMark earned 150 total points
ID: 18030490
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
 
LVL 14

Expert Comment

by:hoomanv
ID: 18031433
Naturally you don't need to implement Heap because java 1.5 already has one
java.util.PriorityQueue
0
 
LVL 35

Accepted Solution

by:
girionis earned 200 total points
ID: 18035174
0

Featured Post

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

By the end of 1980s, object oriented programming using languages like C++, Simula69 and ObjectPascal gained momentum. It looked like programmers finally found the perfect language. C++ successfully combined the object oriented principles of Simula w…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers learn about the “while” loop and how to utilize it correctly in Java. Additionally, viewers begin exploring how to include conditional statements within a while loop and avoid an endless loop. Define While Loop: Basic Example: Explanatio…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …

867 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

17 Experts available now in Live!

Get 1:1 Help Now