sort array using heap sort

Question

class HeapSort{
   public static void main(String args[]){
      int A[]={6,5,4,3,2,1};
      HeapSor obj=new HeapSor(6);
      obj.Heap_Sort(A);
      obj.print(A);
   }
}


class HeapSor{

    int lenOfArray;
    int HeapSize;

    HeapSor(int len){
    this.lenOfArray=len;
    this.HeapSize=len;
    }

    void Heap_Sort(int A[]){
    for(int i=0; i<lenOfArray; i++){
        BuiltHeap(A);
        HeapSize--;
        swap(A,i,lenOfArray-i);
    }
    }

    void BuiltHeap(int A[]){
    for(int i=lenOfArray/2; i>=0; i--)
        MaxHeapify(A,i);
    }

    void MaxHeapify(int A[],int i){
    int l=2*i;
    int r=2*i+1;
    int max=i;

    if(i>HeapSize)
        return;
    if(A[l]>A[r])
        max=l;
    else
        max=r;

    if(A[i]<A[max])
        swap(A,i,max);
    //max=i;
    }

    void swap(int A[],int i,int j){
    if(i==j)
        return;

    int temp=A[i];
    A[i]=A[j];
    A[j]=temp;
    }

    void print(int A[]){
    for(int i=0; i<lenOfArray; i++)
        System.out.print(A[i]+" ");

    System.out.println();
    }
}

when I compiled it gave me this error

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6
    at HeapSor.MaxHeapify(HeapSort.java:41)
    at HeapSor.BuiltHeap(HeapSort.java:31)
    at HeapSor.Heap_Sort(HeapSort.java:23)
    at HeapSort.main(HeapSort.java:5)

I really tried to now what is wrong but I failed plz any one can tell me what is my wrong?

sorry for my bad english

What did you find when tried to debug?

daniel gratzer
– daniel gratzer

2013-02-07 21:36:25 +00:00
Commented Feb 7, 2013 at 21:36 — daniel gratzer
– daniel gratzer, Commented Feb 7, 2013 at 21:36

Mel Nicholson · Accepted Answer · 2013-02-07 21:43:28Z

2

Two problems to start (there will be more).

1) Java is not C. Find the length of A using A.length not passing a separate variable.

2) your calculation of l and r is broken. You pass in 6/2 = 3 you then get 2*3 and 2*3+1 (6 and 7) for your indicies. Neither of those is valid.

answered Feb 7, 2013 at 21:43

Mel Nicholson

3,22416 silver badges25 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Mel Nicholson Over a year ago

For #1, Initialize HeapSor with the array, not a length. Use A.length everywhere you would have used lenOfArray.

Mel Nicholson Over a year ago

For #2, your whole algorithm is incorrect. You need to wiki HeapSort to get the correct algo.

Rezwan4029 · Accepted Answer · 2014-07-16 00:13:46Z

void max_heapify(int a[],int i,int n) {
    int mxPos = i;
    int l = i*2; // left child
    int r = i*2+1; // right child

    if( l <= n and a[l] > a[mxPos] ) mxPos = l;
    if( r <= n and a[r] > a[mxPos] ) mxPos = r;

    if( mxPos != i ) {
        swap( a[i] , a[mxPos] );
        max_heapify( a , mxPos , n );
    }
}

void build_max_heap( int a[] ,int n) {
    for(int i = n / 2 ; i >= 1 ; i-- ) max_heapify(a,i,n);
}

void heapsort(int a[],int n) {
    build_max_heap(a,n);
    for( int i = n ; i >= 2 ; i-- ) {
        swap( a[1] , a[i] );
        n--;
        max_heapify( a , 1 , n );
    }
}

int main() {
    int n , a [100] ;
    cin >> n ;
    for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
    heapsort(a,n);
    for( int i = 1 ; i <= n ; i++ ) cout << a[i] << endl;
}

Cratylus · Accepted Answer · 2013-02-07 21:44:16Z

1

My guess is that your problem is here: void MaxHeapify(int A[],int i)

You assign left and right child:

int l=2*i;  
int r=2*i+1;

But you don't check if they are out of bounds. You check for i.

if(i>HeapSize)  
        return;

But 2*i could be out of bounds and you use it:

 if(A[l]>A[r])  
        max=l;  
    else  
        max=r;

answered Feb 7, 2013 at 21:44

Cratylus

54.3k73 gold badges222 silver badges348 bronze badges

2 Comments

Bassam Badr Over a year ago

changed it to if(i>HeapSize || l>HeapSize || r>HeapSize) still not work

Cratylus Over a year ago

Your algorithm for heapsort is wrong.But you should not be getting any exception.If you do then put the stack trace and show us the line

Yurets · Accepted Answer · 2015-09-16 06:54:59Z

This worked for me:

package Heap;

public class HeapSort {

    private static int[] a;
    private static int n;
    private static int left;
    private static int right;
    private static int largest;

    public static void buildheap(int[] a) {
        n = a.length - 1;
        for (int i = n / 2; i >= 0; i--) {
            maxheap(a, i);
        }
    }

    public static void maxheap(int[] a, int i) {
        left = 2 * i;
        right = 2 * i + 1;
        if (left <= n && a[left] > a[i]) {
            largest = left;
        } else {
            largest = i;
        }

        if (right <= n && a[right] > a[largest]) {
            largest = right;
        }
        if (largest != i) {
            exchange(i, largest);
            maxheap(a, largest);
        }
    }

    public static void exchange(int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    public static void sort(int[] a0) {
        a = a0;
        buildheap(a);

        for (int i = n; i > 0; i--) {
            exchange(0, i);
            n = n - 1;
            maxheap(a, 0);1
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a1 = { 4, 1, 3, 2, 16, 9, 10, 14, 8, 7 };
        sort(a1);
        for (int i = 0; i < a1.length; i++) {
            System.out.print(a1[i] + " ");
        }

    }

}

Collectives™ on Stack Overflow

sort array using heap sort

4 Answers 4

2 Comments

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related