# HeapSort Fehler



## deiwid (9. Apr 2011)

Hallo, hab einen Heap Sort in eclipse programmiert. Wenn kommen in einigen Zeilen Fehlermeldungen, wo ich aber nicht weiß was falsch ist. Kann mir da bitte jemand helfen.


```
import java.util.Arrays;

public class Heap {
	
	private int[] a;
	private int heap_size;
	
	public void Heapsort(int a[]) {
		
        this.a=a;
		maximumHeap(); //Fehlermeldung
		
			for(int i = a.length-1; i>=2; i-- ){
				int tmp = a[1];
				a[1] = a[i];
				a[i] = tmp;
				heap_size--;
				max_heap(a, 1);
			}
	}
	
	
	public void maximumHeap() {
		heap_size = a.length-1;
		
		for(int i = (a.length-1)/2; i>=1; i--){
			max_heap(a, i);                             // Fehlermeldung
		}	
	}
	
	
	public void max_heap(int[] a ,int i) {
		
		int l = 2*i;
		int r = 2*i+1;
		int largest;
		
		if(l>=heap_size && (a[l] > a[i])) {
			largest = l ; }
		else {
			largest = i; }
		
		if(r>=heap_size && (a[r] > a[largest])) {  //Fehlermeldung
			largest = r; }
		
		if(largest!=i) {
			int temp = a[i];
			a[i] = a[largest];
			a[largest]=temp;
			max_heap(a, largest);
		}	
	}
	
		
    public String toString() {
        return Arrays.toString(a); //gibt Array aus
    }

}
```


```
public class Test {

	public static void main ( String[] args){
		
		Heap s = new Heap();
		s.Heapsort(new int[] {12, 56, 4 ,34, 89, 1, 2}); //Fehlermeldung
		s.toString();
	}
}
```

Das kommt als Fehlermeldung: Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 7
	at Heap.max_heap(Heap.java:43)
	at Heap.maximumHeap(Heap.java:27)
	at Heap.Heapsort(Heap.java:11)
	at Test.main(Test.java:7)

Bitte um Lösungshilfe! Danke!


----------



## Marco13 (9. Apr 2011)

Der Array hat eine Länge von 7, also Indizes 0-6

Aufrufkette:

```
s.Heapsort(new int[] {12, 56, 4 ,34, 89, 1, 2}); //Fehlermeldung
..
maximumHeap(); //Fehlermeldung
...
for(int i = (a.length-1)/2; i>=1; i--){ [b]// Hier ist i am Anfang (7-1)/2=3[/b]
    max_heap(a, i);                             // Fehlermeldung
}   
...

// In max_heap:
int r = 2*i+1; [b]// Hier ist r am Anfang 2*3+1=7 (wenn i=3 ist) 
if(r>=heap_size && (a[r] > a[largest])) {  //Fehlermeldung [b] Weil auf index 7 zugegriffen wird[/b]
```

Reicht das als "Lösungshilfe"? Oder wolltest du direkt DIE Lösung? (Da muss man immer so lange nachdenken   )


----------



## deiwid (9. Apr 2011)

also muss ich ich einfach schreiben: int r = 2*i; ohne +1 ?


----------



## Marco13 (9. Apr 2011)

Das würde zwar den Fehler verhindern, aber ob der Algorithmus mit dieser Änderung noch so funktioniert, wie er sollte, kann man auf die Schnelle und nur durch drüberschauen nicht sagen - das muss derjenige, der den Algorithmus implementiert hat, wissen oder sich erarbeiten...


----------

