HeapSort help

[baby_c]

Hello friends..!

I tried to implement HeapSort algorithm in Java. but I've got some problems. First I should say that I have tried to implement the algorithm mentioned in the book "Introduction to Algorithm". the first question is how we can maintain the heap size? The book doesn't help with that. I choose the 0th element of the array as the heap size.
but when I run the program it ended up with bunch of Arrayoutbound errors.. Can you help me out guys..?

thank you in advance.

class heapSort{
    
    int getParent(int i){
        return (int) Math.floor(i/2);
    }

    int getLeft(int i){
        return 2*i;
    }

    int getRight(int i){
        return 2*i+1;
    }

    void maxHeapify(int[] A,int i){
        int l,r,largest;
        l=this.getLeft(i);
        r=this.getRight(i);
        if(l<=A[0] && A[l]>A[i])
            largest=l;
        else
            largest=i;

        if(r<=A[0] && A[r]>A[largest])
            largest=r;
        if(largest!=i){
            A=this.swap(A, A[i], A[largest]);
            maxHeapify(A, i);
        }


    }

    int[] swap(int[] A,int a,int b){
        int temp;
        temp=A[a];
        A[a]=b;
        A[b]=temp;

        return A;


    }

    void buidMaxheap(int[] A){
        A[0]=A.length;
        for(int i=(int) Math.floor((A.length)/2);i>0;i--){
            this.maxHeapify(A, i);
        }
    }

    int[] heapSort(int[] A){
        this.buidMaxheap(A);
        for(int i=A.length;i>2;i--){
            this.swap(A, A[1], A[i]);
            A[0]--;
            this.maxHeapify(A, 1);

        }
        return A;
    }



}

[Taywin]

Could you show us the algorithm written in the book? Is it similar to the pseudo code from WikiPedia (quoted below)?

/*
 function heapSort(a, count) is
     input:  an unordered array a of length count
 
     (first place a in max-heap order)
     heapify(a, count)
 
     end := count-1 //in languages with zero-based arrays the children are 2*i+1 and 2*i+2
     while end > 0 do
         (swap the root(maximum value) of the heap with the last element of the heap)
         swap(a[end], a[0])
         (put the heap back in max-heap order)
         siftDown(a, 0, end-1)
         (decrease the size of the heap by one so that the previous max value will
         stay in its proper placement)
         end := end - 1
 
 function heapify(a, count) is
     (start is assigned the index in a of the last parent node)
     start := count / 2 - 1
     
     while start ≥ 0 do
         (sift down the node at index start to the proper place such that all nodes below
          the start index are in heap order)
         siftDown(a, start, count-1)
         start := start - 1
     (after sifting down the root all nodes/elements are in heap order)
 
 function siftDown(a, start, end) is
     input:  end represents the limit of how far down the heap
                   to sift.
     root := start

     while root * 2 + 1 ≤ end do          (While the root has at least one child)
         child := root * 2 + 1        (root*2 + 1 points to the left child)
         swap := root        (keeps track of child to swap with)
         (check if root is smaller than left child)
         if a[swap] < a[child]
             swap := child
         (check if right child exists, and if it's bigger than what we're currently swapping with)
         if child+1 ≤ end and a[swap] < a[child+1]
             swap := child + 1
         (check if we need to swap at all)
         if swap != root
             swap(a[root], a[swap])
             root := swap          (repeat to continue sifting down the child now)
         else
             return
*/

[baby_c]

Could you show us the algorithm written in the book? Is it similar to the pseudo code from WikiPedia (quoted below)?

/*
 function heapSort(a, count) is
     input:  an unordered array a of length count
 
     (first place a in max-heap order)
     heapify(a, count)
 
     end := count-1 //in languages with zero-based arrays the children are 2*i+1 and 2*i+2
     while end > 0 do
         (swap the root(maximum value) of the heap with the last element of the heap)
         swap(a[end], a[0])
         (put the heap back in max-heap order)
         siftDown(a, 0, end-1)
         (decrease the size of the heap by one so that the previous max value will
         stay in its proper placement)
         end := end - 1
 
 function heapify(a, count) is
     (start is assigned the index in a of the last parent node)
     start := count / 2 - 1
     
     while start ≥ 0 do
         (sift down the node at index start to the proper place such that all nodes below
          the start index are in heap order)
         siftDown(a, start, count-1)
         start := start - 1
     (after sifting down the root all nodes/elements are in heap order)
 
 function siftDown(a, start, end) is
     input:  end represents the limit of how far down the heap
                   to sift.
     root := start

     while root * 2 + 1 ≤ end do          (While the root has at least one child)
         child := root * 2 + 1        (root*2 + 1 points to the left child)
         swap := root        (keeps track of child to swap with)
         (check if root is smaller than left child)
         if a[swap] < a[child]
             swap := child
         (check if right child exists, and if it's bigger than what we're currently swapping with)
         if child+1 ≤ end and a[swap] < a[child+1]
             swap := child + 1
         (check if we need to swap at all)
         if swap != root
             swap(a[root], a[swap])
             root := swap          (repeat to continue sifting down the child now)
         else
             return
*/

no it's little different

PARENT (i)
return floor(i/2)
LEFT (i)
return 2i
RIGHT (i)
return 2i + 1

Heapify (A, i)

l ← left
r ← right
if l ≤ heap-size [A] and A[l] > A
then largest ← l
else largest ← i
if r ≤ heap-size [A] and A > A[largest]
then largest ← r
if largest ≠ i
then exchange A ↔ A[largest]
Heapify (A, largest)

BUILD_HEAP (A)

heap-size (A) ← length [A]
For i ← floor(length[A]/2) down to 1 do
Heapify (A, i)

HEAPSORT (A)

BUILD_HEAP (A)
for i ← length (A) down to 2 do
exchange A[1] ↔ A
heap-size [A] ← heap-size [A] - 1
Heapify (A, 1)

[Taywin]

There are certain issues with the pseudo code you gave above.

- What is left? Is it the same as Left(i)?
- "for i ← length (A) down to 2 do" is obviously wrong because you cannot access an array at A[length(A)]
- The heap-size is a global variable of the class. You must not add it into your array.
- When you call swap(), you should send in array, index1, index2 as arguments. What you send in are the value in the array, not the indices.
- The swap() function should be...

int[] swap(int[] A, int a, int b) {
  int temp;
  temp=A[a];
  A[a]=A[b];
  A[b]=temp;
  return A;
}

[Taywin]

OK, I found a site that wrote the algorithm at here... Surprisingly, the pseudo code of the algorithm is really really really bad...

1)baby_c, you were right about using A[0] as heap-size for this algorithm. This is really silly when you pass in an array. Who on earth would pass an array like that... -_-

2)In Heapify(), line

if r ≤ heap-size [A] and A[i] > A[largest]

should be

if r ≤ heap-size [A] and A[r] > A[largest]

and you did it correctly in your own code.

3)Because A[0] is the heap-size, you need to be careful when the algorithm talks about A.length because it is actually the A.length-1 (not count the A[0]).

4)I still stand on swap() function.

I tried implementing it using this algorithm as I stated above and it works...

PS: Even though the web page states the algorithm as yours, the implementation on the site (at the end of the page) does not exactly follow the step in the algorithm... Surprise, surprise. >:)

[baby_c]

OK, I found a site that wrote the algorithm at here... Surprisingly, the pseudo code of the algorithm is really really really bad...

1)baby_c, you were right about using A[0] as heap-size for this algorithm. This is really silly when you pass in an array. Who on earth would pass an array like that... -_-

2)In Heapify(), line

if r ≤ heap-size [A] and A[i] > A[largest]

should be

if r ≤ heap-size [A] and A[r] > A[largest]

and you did it correctly in your own code.

3)Because A[0] is the heap-size, you need to be careful when the algorithm talks about A.length because it is actually the A.length-1 (not count the A[0]).

4)I still stand on swap() function.

I tried implementing it using this algorithm as I stated above and it works...

PS: Even though the web page states the algorithm as yours, the implementation on the site (at the end of the page) does not exactly follow the step in the algorithm... Surprise, surprise. >:)

:)

[baby_c]

Sorry guys I didn't have much time to peek into this post until now. Sorry for that. And I'd like to say that I found the mistake(s) I made.

1. my Swap method replaces a array value with a array index. :D : Line 41
2. The recursion call of maxHeapify method need largest value as input not the value i : Line 34

here's the complete code.Thanks guys.

class heapSort{

    int getParent(int i){
        return (int) Math.floor(i/2);
    }

    int getLeft(int[] A,int i){
        if(2*i<A.length-1)
            return 2*i;
        else
            return i;
    }

    int getRight(int[] A,int i){
        if(2*i<A.length-1)
            return 2*i+1;
        else
            return i;
    }

    void maxHeapify(int[] A,int i){
        int l,r,largest;
        l=this.getLeft(A,i);
        r=this.getRight(A,i);
        if(l<=A[0] && A[l]>A[i])
            largest=l;
        else
            largest=i;

        if(r<=A[0] && A[r]>A[largest])
            largest=r;
        if(largest!=i){
            A=this.swap(A, i, largest);
            maxHeapify(A, largest);
        }
    }

    int[] swap(int[] A,int a,int b){
        int temp;
        temp=A[a];
        A[a]=A[b];
        A[b]=temp;

        return A;
    }

    void buidMaxheap(int[] A){
        A[0]=A.length-1;
        for(int i=(int) Math.floor((A.length-1)/2);i>0;i--){
            this.maxHeapify(A, i);
        }
    }

    int[] heapSort(int[] A){
        this.buidMaxheap(A);
        for(int i=A.length-1;i>1;i--){
           A= this.swap(A, 1, i);
           A[0]--;
           this.maxHeapify(A, 1);
        }
        return A;
    }

}