Solved

Implementing a heapSort().

Posted on 2006-11-28
3
838 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

PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

Question has a verified solution.

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

Java had always been an easily readable and understandable language.  Some relatively recent changes in the language seem to be changing this pretty fast, and anyone that had not seen any Java code for the last 5 years will possibly have issues unde…
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
Viewers will learn about arithmetic and Boolean expressions in Java and the logical operators used to create Boolean expressions. We will cover the symbols used for arithmetic expressions and define each logical operator and how to use them in Boole…

809 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