sorting using heapsort in java

Question

import java.util.Arrays;

public class Test{

//main method
public static void main(String... args){
    int[] a = new int[]{16,14,10,8,7,9,3,2,4,1};

    System.out.println("unsorted array " + Arrays.toString(a));

    heap_sort(a);

    System.out.println("Sorted array " + Arrays.toString(a));
}

//returns left child index of given index
private static int left_child(int i){
return (i * 2 + 1);
}

//returns right child index of the given index
private static int right_child(int i){
    return (i * 2 + 2);
}


public static void max_heapify(int[] array , int index , int heap_size){
    int largest = index;
    int left = left_child(index);
    int right = right_child(index);

    if(left < heap_size && array[left] > array[index]){
        largest = left;
    }
    else largest = index;

    if (right < heap_size && array[right] > array[largest]){
        largest = right;
    }

    if(largest != index){
        //exchange array[index] with array[largest]
        int a = array[index];
        array[index] = array[largest];
        array[largest] = a;

        max_heapify(array,largest,heap_size);
    }
}

public static void build_max_heap(int[] array){
    int heap_size = array.length - 1;


    for (int i = ((array.length - 1) / 2) ; i >= 0 ; i--){
        max_heapify(array, i, heap_size);
    }
}

//main heap sort function 
public static void heap_sort(int[] array){

    int heap_size = array.length - 1;


    build_max_heap(array);

    for(int i = (array.length - 1) ; i > 0 ; i--){
        //exchange array[0] with array[i]
        int a = array[0];
        array[0] = array[i];
        array[i] = a;

        heap_size = heap_size - 1;
        max_heapify(array , 1 , heap_size);
    }
}


}

I have tried almost every possibility but it doesn't works fine .Could u find out where i am wrong. Output of my code is : unsorted array [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] Sorted array [14, 10, 8, 7, 9, 3, 2, 4, 1, 16]

Krom · Accepted Answer · 2017-04-18 09:46:50Z

There are some problems: - Left and right child are modified because you loose the first element in the array. - In max_heapify function, the loops are <= - In heap_sort function you must pass 0 instead of 1 to the max_heapify function.

  //returns left child index of given index
    private static int left_child(int i)
    {
        return (i * 2);
    }

    //returns right child index of the given index
    private static int right_child(int i)
    {
        return (i * 2 + 1);
    }

    public static void max_heapify(int[] array, int index, int heap_size)
    {
        int largest = index;
        int left = left_child(index);
        int right = right_child(index);

        if (left <= heap_size && array[left] > array[index])
        {
            largest = left;
        }

        if (right <= heap_size && array[right] > array[largest])
        {
            largest = right;
        }

        if (largest != index)
        {
            //exchange array[index] with array[largest]
            int a = array[index];
            array[index] = array[largest];
            array[largest] = a;

            max_heapify(array, largest, heap_size);
        }
    }

    public static void build_max_heap(int[] array)
    {
        int heap_size = array.length - 1;


        for (int i = ((array.length - 1) / 2); i >= 0; i--)
        {
            max_heapify(array, i, heap_size);
        }
    }

    //main heap sort function 
    public static void heap_sort(int[] array)
    {

        int heap_size = array.Length - 1;


        build_max_heap(array);

        for (int i = (array.Length - 1); i > 0; i--)
        {
            //exchange array[0] with array[i]
            int a = array[0];
            array[0] = array[i];
            array[i] = a;

            heap_size = heap_size - 1;
            max_heapify(array, 0, heap_size);
        }
    }

Krom · Accepted Answer · 2017-04-18 09:00:11Z

0

The problem is that you loose items because the left and right child must be:

//returns left child index of given index
private static int left_child(int i){
return (i * 2);
}

//returns right child index of the given index
private static int right_child(int i){
    return (i * 2 + 1);
}

answered Apr 18, 2017 at 9:00

Krom

981 silver badge6 bronze badges

6 Comments

Krom Over a year ago

the result are the same?

Vipin Dubey Over a year ago

Yeah ! results are same.

Krom Over a year ago

ok. Another point: if(left <= heap_size && array[left] > array[index]){ largest = left; } else largest = index; if (right <= heap_size && array[right] > array[largest]){ largest = right; }. You never arrive at the first and last element.

Vipin Dubey Over a year ago

Same output u can see unsorted array [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] Sorted array [14, 10, 8, 7, 9, 3, 2, 4, 1, 16]

Anonymous Over a year ago

When using a 0-based array (as in Java, C and many other languages) for a heap , it standard to use index i * 2 + 1 for left child and i * 2 + 2 for right child.

|

Collectives™ on Stack Overflow

sorting using heapsort in java

2 Answers 2

Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related