Heapify und Heapsort

E

ETlearner

Mitglied
hallo,
ich habe die aufgabe einen programm zu schreiben,derdie methoden heapify und heapsort auf ein array anwendet...

für heapify habe ich einen ansatz... doch leider erhalte ich eine warnung,aber keinen fehler.
heir ist der quellcode:
Java: 
public class HeapSort < T extends Comparable> {
	
	
  
	T[] knoten;
	
	public HeapSort(T[] knoten){
		this.knoten=knoten;
	}
	
	
	void swap(T a,T b){
		T c=a;
		a=b;
		b=c;}
	
	
	private static int getLeftChild( int i) {
    return 2 * i + 1;
  }
 
  private static int getRightChild(int i) {
    return 2 * i + 2;
  }

  
  
public void heapify(){
		
		for (int i= (knoten.length-1)/2; i>=0; i--){
			heapify(i, knoten.length-1);
		}
	}
	
  private void heapify(int i, int end){
  
	int linkeskind=getLeftChild(i);
	int rechteskind=getRightChild(i);
	int biggest;
	
		if(rechteskind>end && linkeskind >end){
			
			if(knoten[i].compareTo(knoten[linkeskind])<0){
				swap(knoten[i], knoten[linkeskind]);}}
			
		else if(rechteskind<=end){
		
			if(knoten[linkeskind].compareTo(knoten[rechteskind])>=0){
				biggest=linkeskind; }
			else{ biggest=rechteskind;}
			
			if(knoten[i].compareTo(knoten[biggest])<0){
				swap(knoten[biggest],knoten[i]);
				}
			heapify(biggest,end);
				
				
			
  }
  
  }
  
  
  
  }

heapsort müsste mithilfe der heapifymethode eigentlich recht einfach sein zu implementieren
Java: 
void heapsort(){
          int sortierterbreich=0;
          while(i<knoten.length){
          knoten.heapify();
          swap(knoten[0],knoten[knoten.length-1]);
          i++;}
doch wie bekomme ich es hin, dass heapify nur noch vom index 0 bis arraylänge-2 läuft und beim nächten schleifendurchlauf von 0bis arraylänge-3?

würde mich sehr auf tipps und verbesserungen freuen
danke im voraus
mfg
etlearner
 
H

HimBromBeere

Top Contributor
doch wie bekomme ich es hin, dass heapify nur noch vom index 0 bis arraylänge-2 läuft und beim nächten schleifendurchlauf von 0bis arraylänge-3?
Zum Vergrößern anklicken....
Indem du deiner Methode einfach das
Code: 
i
mit übergibst und es dann von
Code: 
length
abziehst?

[EDIT]Ach du meine Güte, seh ich das richtig, dass du heapify innerhalb einer Schleife aufrufst UND zusätzlich auch noch eine Rekustion drüber machst? Das klingt ziemlich langsamm, ist nur angenommen, berichtigt mich, wenn ich verkehrt liege (aber über solche Algorithmen mach ich mir kaum Gedanken, darum fehlt mir jetzt auch Detailwissen, ob und wie das besser ginge).[/EDIT]
 
Zuletzt bearbeitet:
E

ETlearner

Mitglied
aber die methode heapify() hat keine übergabeparameter oder?
ja die aufgaben sind extra so gestellt damit man selber mitdenkt und die methoden nicht aus dem internet einfach kopiert :)
ok danke trotzdem :)
 
Zuletzt bearbeitet:
H

HimBromBeere

Top Contributor
Konnte ja keiner wissen, dass du die Methode nicht verändern darfst...

Ich bin aber ein wenig verirrt bzgl. deiner Namensgebung: gehe ich richtig in der Annahme, dass knoten eine Instanz von HeapSort ist?
Und letzte Frage: welches Heapify soll nun eigtl. wie oft laufen? Das "äußere" innerhalb der while-Schleife aufgerufene, also das, welches keine Parameter hat und innerhalb der while-Schleife (heapsort) aufgerufen wird?

Klingt mir alles irgendwie ziemlich chaotisch und verwirrend.
 
Zuletzt bearbeitet:
E

ETlearner

Mitglied
der name des arrays ist knoten und das array ist ein attribut der klasse heapsort.

also in der uni hatten wir folgendes algorithmus für heapify():

1.setze index n/2
2.vollständiges Siftdown auf knoten i
3.dekrementiere i=i-1
4. wiederhole 2.und3. bis i negativ
 
G

greatergood

Mitglied
Also nochmal das Grundprinzip von HeapSort.

Du hast ein Array gegeben, von dem du nicht ausgehen kannst, dass es richtig sortiert ist (wie ein heap). (1)

Noch ist es wichtig zu nennen: handelt es sich um einen "Min-Heap" oder "Max-Heap"?
Min-Heap: Wurzel ist kleinstes element.
Max-Heap: Wurzel ist größtes element.

Nächste wichtige info: Ist dies ein Binär, Trinär oder n-närer Heap?
(meist binär)

Wegen (1) musst du Heapify, auf jeden Knoten (angefangen bei dem letzten) aufrufen. Wenn

du ein Beispiel-Array als (binären Baum) aufzeichnest, merkst du schnell, dass die unterste "Zeile", also die Blätter unspektakulär sind, weil keine Kinder.

Heapify auf einen Knoten soll die HeapEigenschaft überprüfen, d.h. bei Min-Heap:
wähle kleinstes Kind und überprüfe, ob es kleiner ist, als aktueller Knoten, wenn ja -> Swap, wenn nein... nix machen und Heapify aufs nächste.
(Analog umgedrehte logik beim Max-Heap).

Fragen:
* Wieso startet dein "Heapify-Schleifen"-Index "i" bei knoten.length - 1 /2 ??... Muss man nicht einfach beim letzten Element anfangen?
* Was soll das "end" sein?

Wenn du das erklären kannst, können wir vielleicht in deine Implementierung durchblicken, ansonsten ein Tipp:

Schreibe dein Programm wirklich so, wie du es verstehst (bildlich). Ergo: Mach dir die Mühe und Schreibe eine Klasse "Heap" die jeden Wert ihres "Binären-Heap-Baumes" mit einem Index und einem eigentlichen Wert versieht. (dies ist auch ein sehr wichtiger Unterschied: Stelle eines Knotens und dessen Wert zu unterscheiden).


EDIT:
Den Algo, den ich oben beschrieben hab, war halt Thema an unserer Uni. Ich kann also nich garantieren, dass es bei euch auch so abläuft. (p.s. erläutere deinen Heapsort-algo vllt anhand von nem Beispiel??)
 
E

ETlearner

Mitglied
sry für die fehlenden info.

es ist ein maxheap,
es ist ein binärbaum--> heapify ab knoten n/2
heapify soll nicht die heapeigenschaft überprüfen, sondern das array in ein maxheap umwandeln.

bei einem binärbaum ist es nicht notwendig bei dem letzten element anzufangen... erst ab dem index n/2 gibt es in einem binärbaum kinderknoten, die wir mit dem elternknoten vergleichen können.

sry für das durcheinander
lg
 
E

ETlearner

Mitglied
habe den quellcode kommentiert :)
hoffe so ist es verständlicher

Java: 
public class HeapSort < T extends Comparable> {
    
    
  
    T[] knoten;				
    
    public HeapSort(T[] knoten){
        this.knoten=knoten;
    }
    
    
    void swap(T a,T b){
        T c=a;
        a=b;
        b=c;}
    
    
    private static int getLeftChild( int i) {
    return 2 * i + 1;
  }
 
  private static int getRightChild(int i) {
    return 2 * i + 2;
  }
 
  
  
public void heapify(){			// heapify() soll ein array so ändern, sodass array heapeigenschaft erfüllt
        for (int i= (knoten.length-1)/2; i>=0; i--){ // index startet ab n/2
            heapify(i, knoten.length-1);
        }
    }
    
  private void heapify(int i, int end){
  
    int linkeskind=getLeftChild(i);
    int rechteskind=getRightChild(i);
    int biggest;
    
        	if(rechteskind>end && linkeskind <=end){	// wenn der index des rechten kindes größer als die arraylänge ist und das linke kind kleiner
			
			if(knoten[i].compareTo(knoten[linkeskind])<0){ //, so vergleiche elternknoten mit linken kindknoten
				swap(knoten[i], knoten[linkeskind]);}}	//wenn elternknoten<linker kindknoten, dann vertausche sie
			
		else if(rechteskind<=end){// wennd der index des rechten kindknotens kleiner als die arraylänge ist, so ist auch der index des linkes kindknotens kleiner als die arraylänge
		
			if(knoten[linkeskind].compareTo(knoten[rechteskind])>0){ //welches der kinderknoten ist größer->biggest
				biggest=linkeskind; }
			else{ biggest=rechteskind;}
			
			if(knoten[i].compareTo(knoten[biggest])<0){//vergleiche biggest mit elternknoten... wenn elternknoten kleiner als biggest vertausche sie
				swap(knoten[biggest],knoten[i]);
				}
			heapify(biggest,end);
				
				
			
  }
  
  }
  
  
  
  }

lg
 
E

ETlearner

Mitglied
ich habe ein paar fehler beseitigt...
die klasse sollte so beginnen:
public class HeapSort < T extends Comparable<T>> {...

nun habe ich keine warnungen auf der console...

von der implementierung her ist es meiner meinung nach richtig... ABER es werden nie elemente in der testklasse miteinander getausch... in der testklasse ist T ein string...
also kann die swapmethode garnicht klappen-> call by value
wie könnte ich trotzem swap so ändern, sodass elemente in dem array knoten vertauscht werden?

lg
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
D Heapsort - wie? Java Basics - Anfänger-Themen 2
B HeapSort Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Aktuelle Jobs

Neue Themen


Oben