Code For Binary Heapsort

Question

I am practicing writing codes from pseudocodes. I found this while going over my Introductions to Algorithms text. I am sure I coded precisely to the pseudocode, however; it is not outputing what I want. The code is a Binary Heapsort. Instead of sorting my input, the code returns my input unchanged as an output. My thoughts towards the problem exist in the build method, where I casted Math.floor() to an int. This is my first time using floor(), so I believe my lack of understanding is the problem. I believe that I am returning the lowest approximated value of heapsize/2 so I could branch my Binary Heap. But is this the case in my coding?

public class tester
{
public static void heapsort(int[] a)
{

    build(a);

    for (int i = a.length - 1; i >= 1; i--)
    {
        swap(a, 0, i);
        int heapsize = a.length - 1;
        heapify(a,0);
    }
}

public static void build(int[] a)
{
    int heapsize = a.length;
    int fl = (int) Math.floor((heapsize)/2);
    for (int i = fl; i >= 0; i--)
    {
        heapify(a, i);
    }
}

public static void heapify(int[] a, int root)
{
    int left = 2 * root + 1;
    int right = 2 * root + 2;
    int heapsize = a.length;
    int largest;

    if ( (left < heapsize) && (a[left] > a[root]))
    {
        largest = left;
    }
    else
    {
        largest = root;
    }
    if ( (right < heapsize) && (a[right] > a[largest]))
    {
        largest = right;
    }
    if (largest != root)
    {
        swap(a, a[root], a[largest]);
        heapify(a, largest);
    }

}

public static void swap(int[] a, int x, int y)
{
    int tmp;
    tmp = a[x];
    a[x] = a[y];
    a[y] = tmp;
}

public static void main(String[] args)
{
    int[] a = new int[args.length];
    for (int i = 0; i < args.length; i++)
    {
        a[i] = Integer.parseInt(args[i]);
    }
    heapsort(a);
    for (int i : a)
    {
            System.out.println(i);
        }
    }
}

I'm sorry, I haven't used StackOverFlow until recently when I picked up coding. I saw others post full outlines of their code so I thought I could do the same. — user3339453
– user3339453, Commented Feb 27, 2014 at 5:39
I meant in the description of the code, using the `. Also I am rather new to stack over flow too. — PlasmaPower
– PlasmaPower, Commented Feb 27, 2014 at 5:43

Njol · Accepted Answer · 2014-02-27 05:44:57Z

2

Your swap method doesn't work in Java, as you can only pass primitives by value, not by reference. You can modify the method like this:

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

This would then be called like

    swap(a, 0, i);

instead of

    swap(a[0], a[i]);

And will correctly swap two numbers in the array.

answered Feb 27, 2014 at 5:44

Njol

3,28920 silver badges32 bronze badges

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

2 Comments

user3339453 Over a year ago

Thank you for directing that to me, the output is still returning my input unchanged.

user3339453 Over a year ago

Thank you, I figured out my mistake

Mohsen Kamrani · Accepted Answer · 2014-02-27 06:24:48Z

0

you should correct the heapify this way :

public static void heapify(int[] a, int root)
{

    int left = 2 * root + 1;
    int right = 2 * root + 2;
    int heapsize = a.length;
    int largest;

    if ( (left < heapsize) && (a[left] > a[root]))
    {
        largest = left;
    }
    else
    {
        largest = root;
    }
    if ( (right < heapsize) && (a[right] > a[largest]))
    {
        largest = right;
    }
    if (largest != root)
    {
        swap(a, root, largest);
        heapify(a, largest);
    }

}

so your total code will be :

public class tester
{
public static void heapsort(int[] a)
{

    build(a);

    for (int i = a.length - 1; i >= 1; i--)
    {
        swap(a, 0, i);
        int heapsize = a.length - 1;
        heapify(a,0);
    }
}

public static void build(int[] a)
{
    int heapsize = a.length;
    int fl = (int) Math.floor((heapsize)/2);
    for (int i = fl; i >= 0; i--)
    {
        heapify(a, i);
    }
}

public static void heapify(int[] a, int root)
{

    int left = 2 * root + 1;
    int right = 2 * root + 2;
    int heapsize = a.length;
    int largest;

    if ( (left < heapsize) && (a[left] > a[root]))
    {
        largest = left;
    }
    else
    {
        largest = root;
    }
    if ( (right < heapsize) && (a[right] > a[largest]))
    {
        largest = right;
    }
    if (largest != root)
    {
        swap(a, root, largest);
        heapify(a, largest);
    }

}

public static void swap(int[] a, int x, int y)
{
    int tmp;
    tmp = a[x];
    a[x] = a[y];
    a[y] = tmp;
}

public static void main(String[] args)
{
    int[] a = new int[args.length];
    for (int i = 0; i < args.length; i++)
    {
        a[i] = Integer.parseInt(args[i]);
    }
    heapsort(a);
    for (int i : a)
    {
        System.out.println(i);
    }
}
}

answered Feb 27, 2014 at 6:24

Mohsen Kamrani

7,5075 gold badges48 silver badges73 bronze badges

3 Comments

user3339453 Over a year ago

I've already done the fix with the swap() in heapify(). I think my problem is in the heapsort method. I am returning my unsorted input.

Mohsen Kamrani Over a year ago

First please try the code I've sent, I works for me! you can test it with sth like this: int[] a = {1,3,5,4,2,9};

Mohsen Kamrani Over a year ago

OMG, I've just found an exception, you're right the code doesn't work right, and probably the logic of your code is wrong.

Collectives™ on Stack Overflow

Code For Binary Heapsort

2 Answers 2

2 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related